```cpp // https://dashoj.com/d/lqbproblem/p/46 #include <bits/stdc++.h> #define N 100010 using namespace std; typedef long long ll; ll n, k, ans = 0; vector<ll> ls(N, 0); vector<ll> qzh(N, 0); vector<ll> cnt(N, 0); int main() { cin >> n >> k; for (int i = 1; i <= n; i++) cin >> ls[i]; for (int i = 1; i <= n; i++) qzh[i] = qzh[i - 1] + ls[i]; cnt[0] = 1; for (int i = 1; i <= n; i++) { ans += cnt[qzh[i] % k]; cnt[qzh[i] % k]++; } cout << ans << endl; return 0; } // 看完题解大彻大悟 ```

``` #include <bits/stdc++.h> #define endl '\n' typedef long long ll; using namespace std; //数据结构在这里定义 const int N =1e6+10; int a[N]; ll sum[N];//求和要ll int cnt[N];//收集余数为i的 sum区间个数 void solve(){ int n,k; cin >> n >> k; for(int i = 1; i <= n; i++){ cin >> a[i]; //初始化前缀和 sum[i] = sum[i-1] + a[i]; } ll res = 0; //余数为0的区间，哪怕只有一个，也能组成一个K倍区间 //只有它初始值为1 cnt[0] = 1; for(int i = 1; i <= n; i++){ cnt[sum[i] % k]++; //记录下 余数为 x 的 sum前缀和区间有多少 } //收集每个余数的情况 for(int i = 0; i < k;i++){ //cnt[0]=1 保证了只有一个区间余数为0时 //让cnt[0]=2 res能正确的 + 1 //如果没有余数为0的区间 res + 0 res += cnt[i] * (cnt[i] - 1) / 2; //如果有n个区间余数都是m,从中任取两个做差 //[i,j]这个区间的余数变成0即是k倍区间 C n 2 } cout << res << endl; } int main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t;//多组数据要cin //cin >> t; t = 1; while(t--){ solve(); } return 0;//必须加return 0 } ```

``` n,k = map(int,input().split()) ls = [0]+[0]*(n) sumls =[0]+[0]*n cnt = [0]*k for i in range(1,n+1): ls[i] = int(input()) sumls[i] = sumls[i-1] + ls[i] ans = 0 cnt[0]+=1 for i in range(1,n+1): ans += cnt[sumls[i]%k] cnt[sumls[i]%k] +=1 print(ans) ```

```cpp #include <bits/stdc++.h> using namespace std; #define int long long #define endl '\n' const int N = 1e5 + 10; int n, k; int a[N]; int cnt[N]; void solve() { cin >> n >> k; for (int i = 1; i <= n; i++) { cin >> a[i]; a[i] += a[i - 1]; } int res = 0; cnt[0] = 1; // 区间长度可以是1，余数为0表示可以被自身整除，也算一种 for (int i = 1; i <= n; i++) { res += cnt[a[i] % k]; cnt[a[i] % k]++; // 余数为a[i] % k的数的个数+1 } cout << res << endl; } signed main() { std::ios::sync_with_stdio(0); cin.tie(0), cout.tie(0); solve(); return 0; } ```

``` #include #define int long long using namespace std; const int N=1e5+10; int n,k; int sum[N]; int cnt[N];//计算能被k%的数 int ans=0;//计数 signed main() { cin>>n>>k; cnt[0]=1; for(int i=1;i<=n;i++){ cin>>sum[i]; sum[i]+=sum[i-1];//前缀和 ans+=cnt[sum[i]%k]; cnt[sum[i]%k]++; } cout<<ans; return 0; } ```

``` #include<bits/stdc++.h> using namespace std; typedef long long ll; const int N = 1e5+10; ll n,k,x; ll sum[N]; ll cnt[N]; ll res; int main(){ cin>>n>>k; for(int i=1; i<=n; i++){ cin>>x; sum[i]=sum[i-1]+x; } cnt[0] = 1; for(int i=1; i<=n; i++){ res+=cnt[sum[i]%k]; cnt[sum[i]%k]++; } cout<<res<<endl; return 0; } ```

``` #include<bits/stdc++.h> using namespace std; const int N=1e5+10; using ll=long long; int a[N],cnt[N]; ll s[N],ans; int main(){ ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); int n,k;cin>>n>>k; cnt[0]=1; for(int i=1;i<=n;i++){ cin>>a[i]; s[i]=s[i-1]+a[i]; ans+=cnt[s[i]%k]; cnt[s[i]%k]++;//利用同余原理，当余数相同的前缀合相减得到的区间必定是k的倍数 } cout<<ans; return 0; } ```