前缀和数组+数论中的组合思想优化
摘要：解题思路: 这是蓝桥杯2017年B组的最后一道编程题。 首先此题想到前缀和的思想，用前缀和数组的两项相减得到字串之和，能通过33%的数据，差不多是N<=1000左右时能通过。 其次如果想要100%通……
蓝桥杯2017年第八届真题-k倍区间 巧妙的结算
参考了别人的题解```cpp#includeusingnamespacestd;intn,k;longlongnum[100005];//注意longlong不然范围不够！！！intcnt[100005];longlongans;//这里也是！！！intmain(){cin>>n>>k;for(int
蓝桥杯2017年第八届真题-k倍区间【前缀和+数学优化】
最先想到的应该是静态的前缀和，利用前缀和求区间和：不多说了，比较简单，就是求Ai~Aj的和```cpp#includeusingnamespacestd;intn,k;intA[100001];intsum[100001];intcnt=0;intmain(){cin>>n>>k;for(inti=1
蓝桥杯2017年第八届真题-k倍区间 （Java代码）
摘要：解题思路:气死我了，写道一半，突然没网了，然后写的东西全不见了，生气！ 这道题，暴力不可以，所以需要想办法。用数学思维来想一想 1，2，3，4……
蓝桥杯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++代码）
摘要：解题思路:注意事项:参考代码:#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#de……
蓝桥杯2017年第八届真题-k倍区间 （C++代码）前缀和O(n)算法
```求区间和，可以通过前缀和来得到各个区间的和。A[i]表示第1个元素到第i个元素的和。那么A[r]-A[l-1]就是区间[l,r]的和。区间[l,r]的和如果是k的倍数，那么(A[r]-A[l-1])%k==0即A[r]%k==A[l-1]%k那么可以求出每个前缀和，
蓝桥杯2017年第八届真题-k倍区间-题解(C++代码)
思路：前缀和，用sum[i]表示前i项和，那么区间[l,r]的和就是sum[r]-sum[l-1]，因为要是k的倍数，所以(sum[r]-sum[l-1])%k==0，整理一下就是sum[r]%k==sum[l-1]%k，所以统计让这个式子成立的项就好了。
k倍区间 (Java代码）
摘要：import java.util.Scanner;
public class Main {
public static void main(String []args){
……