1.暴力
超时
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 100010;
int s[N],a[N];
int cnt;
int main()
{
int n,k;
cin>>n>>k;
for(int i=1;i<=n;i++)
{
cin>>a[i];
s[i] = s[i-1]+a[i];
}
for(int i=1;i<=n;i++)
{
for(int j=i;j<=n;j++)
{
if((s[j]-s[i-1])%k == 0) cnt++;
}
}
cout<<cnt;
return 0;
}
2.
两个数的差模k==0, 即两个数的模k相同
区间[l,r]的和是k的倍数即(sum[r] - sum[l-1])%k == 0 即sum[r]%k == sum[l-1]%k
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
const int N = 100010;
LL s[N];
int cnt[N]; //余数为i的个数
LL res=0;
int main()
{
int n,k;
cin>>n>>k;
for(int i=1;i<=n;i++)
{
cin>>s[i];
s[i] += s[i-1];
}
cnt[0]++; //s11 = s1-s0 对于这第一个数,该数本身作为子序列
for(int i=1; i<=n; i++) //要么这里从0开始,要么赋值cnt[0]=1. 否则将会忽略第一个数本身作为子序列s11
{
//cout<<s[i]<<"余数: "<<s[i]%k<<endl;
res += cnt[s[i]%k];
//cout<<res<<endl;
cnt[s[i]%k] ++ ;
}
cout<<res;
return 0;
}