解题思路:
注意事项:
1、数据比较多(n=1e5),建议用scanf读入
2、最坏的情况前缀和是10万的平方,1e10,int最多2x10^9,开long long,ans也是
3、时间复杂度->o(n^2)约为1e10超限
for(int i=1;i<=n;i++)
for(int j=i;j<=n;j++)
{
sum=s[j]-s[i-1];
if(sum%k==0)
ans++;
}
参考代码:
#include<iostream>
using namespace std;
typedef long long LL;
const int N=100010;
LL s[N],cnt[N],res;
int n,k;
int main()
{
cin>>n>>k;
for(int i=1;i<=n;i++)
{
cin>>s[i];
s[i]=s[i-1]+s[i];
}
cnt[0]=1;//就是我们这样做我们少计算了区间[0,i]构成的k倍区间,其个数为cnt[0]=1,故加上。
for(int i=1;i<=n;i++)
{
cnt[s[i]%k]++;
}
for(int i = 0; i < k; i++) { //余数必然在0~k-1之间
res += cnt[i] * (cnt[i] - 1) / 2;//Cn2就是要选两个前缀和相减,n(n-1)/2
}
cout<<res<<endl;
}
0.0分
1 人评分
C语言训练-列出最简真分数序列* (C语言代码)浏览:506 |
C语言程序设计教程(第三版)课后习题6.1 (C语言代码)浏览:668 |
WU-链表数据求和操作 (C++代码)浏览:1318 |
2005年春浙江省计算机等级考试二级C 编程题(2) (C语言代码)浏览:648 |
C语言程序设计教程(第三版)课后习题8.8 (C语言代码)浏览:863 |
简单的a+b (C语言代码)浏览:578 |
【亲和数】 (C语言代码)浏览:600 |
格式化数据输出 (C语言代码)浏览:822 |
分解质因数 (C++代码)浏览:1482 |
C语言训练-字符串正反连接 (C语言代码)浏览:632 |