前缀和数组+数论中的组合思想优化
摘要：解题思路: 这是蓝桥杯2017年B组的最后一道编程题。 首先此题想到前缀和的思想，用前缀和数组的两项相减得到字串之和，能通过33%的数据，差不多是N<=1000左右时能通过。 其次如果想要100%通……
蓝桥杯2017年第八届真题-k倍区间【前缀和+数学优化】
最先想到的应该是静态的前缀和，利用前缀和求区间和：不多说了，比较简单，就是求Ai~Aj的和```cpp#includeusingnamespacestd;intn,k;intA[100001];intsum[100001];intcnt=0;intmain(){cin>>n>>k;for(inti=1
蓝桥杯2017年第八届真题-k倍区间 巧妙的结算
参考了别人的题解```cpp#includeusingnamespacestd;intn,k;longlongnum[100005];//注意longlong不然范围不够！！！intcnt[100005];longlongans;//这里也是！！！intmain(){cin>>n>>k;for(int
1882: 蓝桥杯2017年第八届真题-k倍区间(3.17)
解题思路:如果把所有区间分为k倍区间和非k倍区间,观察一下他们之间的区别,k倍区间的和modk后等于0,而非k倍区间的和modk后等于n,n是介于1至k-1的数.再来思考一下如何得到k倍区间,第一种情况,本身就是k倍区间,不那么用做任何操作,
1882: 蓝桥杯2017年第八届真题-k倍区间
摘要：解题思路:注意事项:1、数据比较多（n=1e5）,建议用scanf读入2、最坏的情况前缀和是10万的平方，1e10,int最多2x10^9，开long long,ans也是3、时间复杂度->o(n^2……
蓝桥杯2017年第八届真题-k倍区间
摘要：解题思路: sum[i]表示前i项的和，如果（sum[j] - sum[i]）%k ==0（i<=j），即sum[i]%k==sum[j]%k,则区间[i+1,j]之和是k的倍数，然后用sum[i……
蓝桥杯2017年第八届真题-k倍区间-题解（C++代码）
###解题思路：s[i]表示1~i的前缀和，每次累加i下标前，s[i]%k的余数的个数，就是一个k倍区间。这里有些难理解，例如：s[t]表示1~t的前缀和，他们模k的余数为p，那么当s[i](i>k)模k的余数也为p时，就证明t~i这一段和模k是等于0的，正好是k的倍数。
蓝桥杯2017年第八届真题-k倍区间-题解（C++代码）
摘要：解题思路: 1、 N 的范围上限是100,000，直接枚举 i 和 j 必然超时，所以使用前缀和将 Ai+1 + …… + Aj 变为 Sj - ……
蓝桥杯2017年第八届真题-k倍区间-题解（C++代码）
```cpp/*k倍区间给定一个长度为N的数列，A1,A2,...AN，如果其中一段连续的子序列Ai,Ai+1,...Aj(ia[i];modK[i]=(modK[i-1]+a[i])%k;ans+=cnt[modK[i]];//同模数做差后模k等于0，