题目描述
给定一个长度为N的数列，A1, A2, ... AN，如果其中一段连续的子序列Ai, Ai+1, ... 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
一开始只会暴力解法可以求1000以内不超限
#include<bits/stdc++.h> using namespace std; int main(){ long long s[100010]={0}; map<int,long long>cnt; long long a[100010]={0}; long long n,k; cin>>n>>k; s[0]=0; cnt[0]=1; for(int i=1;i<=n;i++){ cin>>a[i]; s[i]=(s[i-1]+a[i])%k; cnt[s[i]]++; } long long ans=0; for(int i=0;i<k;++i){ ans+=(long long)(cnt[i]*(cnt[i]-1)/2); } cout<<ans<<endl; return 0; }
然后暴力解法升级可以10000以内不超限制
#include<bits/stdc++.h> using namespace std; int main(){ int n,k; cin>>n>>k; int a[100010]; int s[100010]; s[0]=0; for(int i=1;i<=n;i++){ cin>>a[i]; s[i]=s[i-1]+a[i]; } long long ans=0; for(int i=1;i<=n;i++){ for(int j=i;j<=n;j++){ if((s[j]-s[i-1])%k==0)ans++; } } // for(int i=1;i<=n;i++){ // printf("%d\n",s[i]); // } cout<<ans<<endl; return 0; }
最后采取数学思维才能最终做对
#include<bits/stdc++.h> using namespace std; int main(){ long long s[100010]={0}; map<int,long long>cnt; long long a[100010]={0}; long long n,k; cin>>n>>k; s[0]=0; cnt[0]=1;//这个非常关键相当于是本身没有减去任何数 for(int i=1;i<=n;i++){ cin>>a[i]; s[i]=(s[i-1]+a[i])%k; cnt[s[i]]++; } long long ans=0; for(int i=0;i<k;++i){ ans+=(long long)(cnt[i]*(cnt[i]-1)/2); } cout<<ans<<endl; return 0; }
还找到了一个更加简便的做法
#include <iostream> using namespace std; int main() { int x, y; long long num;//k倍区间个数可能很多，所以使用long long数据类型 cin >> x >> y; long long arr[100010] = { 0 };//保存序列的每个数的余数 long long ans[100010] = { 0 };//保存相同余数的数字的个数 num = 0; for (int i = 1; i <= x; i++) { cin >> arr[i]; arr[i] += arr[i - 1]; // cout<<"arr[]"<<i<<arr[i]<<endl; arr[i] = arr[i] % y; num += ans[arr[i]]; // cout<<arr[i]<<endl<<"num"<<num<<endl<<ans[arr[i]]<<endl; ans[arr[i]]++; //cout<<ans[arr[i]]<<endl<<endl; } cout << num + ans[0];//由于num没有加上[0,x]区间上的个数，所以要加上ans[0] return 0; }
