三合一网站建设系统,怎么推广引流客户,展厅布置,vue做网站的好处是什么解题思路
任何两个前缀区间的和对k取模的值相等#xff0c;则由大的前缀区间减掉小的前缀区间所形成的区间的必定是K倍区间。因此我们可以对具有区间和%k值相等任何两个区间进行组合#xff0c;再将这些值加起来就得到结果#xff01;证明#xff1a; 假设一个数列为a1,a2…
解题思路
任何两个前缀区间的和对k取模的值相等则由大的前缀区间减掉小的前缀区间所形成的区间的必定是K倍区间。因此我们可以对具有区间和%k值相等任何两个区间进行组合再将这些值加起来就得到结果证明 假设一个数列为a1,a2,a3,…,an一个小的前缀区间s1为a1,a2,a3,…,ap,还有一个大的前缀区间s2为a1,a2,a3,…,a(pm)p,pmn。当我们对s1、s2的和分别取模得到(a1a2a3…ap)%k和(a1a2a3…apm)%k当这两个值相等的时候。我们则可以列出这个等式(a1a2a3…ap)%k-(a1a2a3…apm)%k0根据取模也具有分配律可得到(a1a2a3…ap-a1-a2-a3-…-apm)%k0。因此可以推出结论s2-s1得出的区间必定为k倍区间。
代码实现
#include iostream
using namespace std;
long long a[100010];
long long cnt[100010];
long long ans 0;
int main()
{cnt[0];int n, k; cin n k;for(int i 1; i n; i){cin a[i];a[i] a[i-1];}for(int i 1; i n; i) ans cnt[a[i] % k];cout ans;return 0;
}
