1 条题解
-
0
我们先看理解相对容易的一种情况,给定区间 ,如果区间 是 的倍数,那么答案加 ,如果 也是 的倍数,那么答案为 ,因为区间 , , ,都是 的倍数。
现在再次给定区间 不过此时 不再是 的整数倍,而是 等于一个整数 ,如果 也是 等于整数 ,此时答案加 ,因为 为 的整数倍。当然如果末尾再加上区间 ,并且 等于整数 的话,答案为 ,因为此时 , , 皆为 的整数倍。
参考答案:
#include<iostream> using namespace std; typedef long long LL; const int N = 100010; LL a[N], cnt[N]; LL n, k, res; int main() { cin >> n >> k; cnt[0] = 1; for (int i = 1; i <= n; ++i) { scanf("%lld", &a[i]); a[i] += a[i - 1]; res += cnt[a[i] % k]; cnt[a[i] % k]++; } cout << res << endl; return 0; }
- 1
信息
- ID
- 5394
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 3
- 标签
- 递交数
- 10
- 已通过
- 4
- 上传者