开发一个网站需要多少人,智邦国际erp系统登录,国内外网站建设比较,怎样做网站制作团队题干#xff1a;
http://lx.lanqiao.cn/problem.page?gpidT444
问题描述 给定一个长度为N的数列#xff0c;A1, A2, ... AN#xff0c;如果其中一段连续的子序列Ai, Ai1, ... Aj(i j)之和是K的倍数#xff0c;我们就称这个区间[i, j]是K倍区间。 你能求出数列中…题干
http://lx.lanqiao.cn/problem.page?gpidT444
问题描述 给定一个长度为N的数列A1, A2, ... AN如果其中一段连续的子序列Ai, Ai1, ... Aj(i j)之和是K的倍数我们就称这个区间[i, j]是K倍区间。 你能求出数列中总共有多少个K倍区间吗
输入格式 第一行包含两个整数N和K。(1 N, K 100000) 以下N行每行包含一个整数Ai。(1 Ai 100000)
输出格式 输出一个整数代表K倍区间的数目。
样例输入
5 2 1 2 3 4 5
样例输出
6 解题报告 首先看到连续区间想到前缀和看到数据范围想想可否满足某个递推关系即知道了某一个区间是k倍区间相应的可以推出另外的区间也是k倍区间。或者预处理出某些值方便得到我们想要的结果。 可以想出mod k 同余的两段区间合并起来肯定是%k0的所以我们预处理出前缀和的余数。代码就不难写了。
AC代码大一的代码了、、、怀念逝去的时光啊顺便吐槽一下当时写代码的稚嫩
#includeiostream
using namespace std;
int yu[1000005];
int a[1000005];
int main()
{int n,k;long long int cnt0;//用int有一个案例过不了 scanf(%d%d,n,k);for(int i1;in;i){scanf(%d,a[i]);a[i](a[i]a[i-1])%k; //一般的前缀和 a数组 要开longlong因为他是累加的和啊可能很大呢这也给我们个提示需要在这里同时进行求余 yu[a[i]]; //这也是为什么i从1开始而不从0开始的原因、 }for(int i0;ik;i){//cnt( yu[i] * (yu[i]-1))/2; //cnt(yu[i]*yu[i-1])/2;cnt( (yu[i]/2.0) * ( (yu[i]-1)/2.0 ))*2; //cnt( (yu[i]/2) * ( (yu[i]-1)/2 ))*2; }cntyu[0];printf(%lld,cnt);return 0 ; }
//5 2
//1
//2
//3
//4
//5
AC代码2标解
#includeiostream
using namespace std;
typedef long long ll;
ll bk[100010] {0};
ll arr[1000010];
int main()
{ int n,k;scanf(%d%d,n,k);for(int i 0; i n; i)scanf(%lld,arr[i]);arr[0] % k;ll sum 0;for(int i 1; i n; i)arr[i] (arr[i]arr[i-1])%k;for(int i 0; i n; i)sum (bk[ arr[i] ]);printf(%lld,sumbk[0]);return 0;
}
