解题思路:原本想利用前缀和解决问题,但是看到数据量如此庞大就知道需要进行优化了 核心就是 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语言代码)浏览:1661 |
【明明的随机数】 (C++代码)浏览:781 |
求组合数 (C语言代码)浏览:1159 |
WU-C语言程序设计教程(第三版)课后习题11.11 (C++代码)(想学链表的可以看看)浏览:1358 |
【魔板】 (C++代码)(时间超限,希望会的帮我改正一下)浏览:745 |
2003年秋浙江省计算机等级考试二级C 编程题(2) (C语言代码)浏览:594 |
用筛法求之N内的素数。 (C语言代码)浏览:669 |
1642题解浏览:716 |
1048题解(读入回车问题)浏览:566 |
简单的a+b (C语言代码)浏览:416 |