P8649 [蓝桥杯 2017 省 B] k 倍区间
题目描述
给定一个长度为 N N N 的数列， A 1 , A 2 , ⋯ A N A_1,A_2, \cdots A_N A1,A2,⋯AN，如果其中一段连续的子序列 A i , A i + 1 , ⋯ A j ( i ≤ j ) A_i,A_{i+1}, \cdots A_j(i \le j) Ai,Ai+1,⋯Aj(i≤j) 之和是 K K K 的倍数，我们就称这个区间 [ i , j ] [i,j] [i,j] 是 K K K 倍区间。
你能求出数列中总共有多少个 K K K 倍区间吗？
输入格式
第一行包含两个整数 N N N 和 K K K ( 1 ≤ N , K ≤ 1 0 5 ) (1 \le N,K \le 10^5) (1≤N,K≤105)。
以下 N N N 行每行包含一个整数 A i A_i Ai ( 1 ≤ A i ≤ 1 0 5 ) (1 \le A_i \le 10^5) (1≤Ai≤105)。
输出格式
输出一个整数，代表 K K K 倍区间的数目。
输入输出样例 #1
输入 #1
5 2
1
2
3
4
5
输出 #1
6
说明/提示
时限 2 秒, 256M。蓝桥杯 2017 年第八届
思路：求出前缀和 然后两重for循环枚举每一个子段是否满足要求，但超时了。 于是使用同余定理优化。
同余定理：给定两个整数A,B，当A%K==B%K时，
(A-B)%K==0
因为 A%K==R 即A=q1K+R,同样的B=q2K+R;
A-B=（q1-q2）*K那么 (A-B)%K=0
求出每个前缀和对K的余数，当余数相同时，两个前缀和相减，此子段可以整除K。当有多个余数时，排列组合公式为n(n-1)/2
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;ll n;
ll k;
ll ans=0;
ll arr[100005];//存余数
ll cnt[100000];
int main()
{cin>>n>>k;for(int i=1;i<=n;i++){cin>>arr[i];arr[i]=arr[i-1]+arr[i];}for(int i=1;i<=n;i++){if(arr[i]%k==0){ans++;}cnt[arr[i]%k]++; } for(int i=0;i<k;i++){ans+=(cnt[i]*(cnt[i]-1))/2;}cout<<ans;return 0;
}
)