【K倍区间】
题目
思路
是 k的倍数
&&
&&
代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
typedef long long ll;
ll s[N], cnt[N];
int main()
{
int n, k;
cin >> n >> k;
for(int i = 1; i <= n; i++)
{
cin >> s[i];
s[i] += s[i-1];
}
ll ans = 0;
cnt[0]++;
int t;
for(int i = 1; i <= n; i++)
{
t = s[i] % k;
ans += cnt[t]; //1.(sj-si)是k的倍数 等价于 2.sj-si>=k && sj与si模k同余 等价于 3.sj与si模k同余(因为同余条件下sj-si<k不成立)
cnt[t]++;
}
cout << ans;
return 0;
}