解题思路:原本想利用前缀和解决问题,但是看到数据量如此庞大就知道需要进行优化了 核心就是 a mod k == b mod 时,|a-b| mod k==0 利用这个就可以进行优化
注意事项:
参考代码:
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+5;
int s[N],a[N],ans;
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n,k;
cin>>n>>k;
vector<int> a[k+1];
for(int i=1;i<=n;i++){
cin>>s[i];
s[i]+=s[i-1];
int m=s[i]%k;
if(m==0){ans++;}
ans+=a[m].size();
a[m].push_back(i);
}
cout<<ans<<endl;
return 0;
}
0.0分
1 人评分
C二级辅导-温度转换 (C语言代码)浏览:2345 |
IP判断 (C语言代码)浏览:924 |
母牛的故事 (C语言代码)浏览:1716 |
C语言程序设计教程(第三版)课后习题5.7 (C语言代码)浏览:689 |
点我有惊喜!你懂得!浏览:2072 |
C语言训练-角谷猜想 (C++代码)(3N+1问题)浏览:1750 |
求组合数 (C语言代码)浏览:1159 |
C语言程序设计教程(第三版)课后习题1.5 (C语言代码)浏览:473 |
1009题解浏览:752 |
C语言程序设计教程(第三版)课后习题1.5 (C语言代码)浏览:470 |