题目描述
There are N boxes arranged in a row from left to right. The i-th box from the left contains Ai candies.
You will take out the candies from some consecutive boxes and distribute them evenly to M children.
Such being the case, find the number of the pairs (l,r) that satisfy the following:
l and r are both integers and satisfy 1≤l≤r≤N.Al+Al+1+…+Ar is a multiple of M.
Constraints
·All values in input are integers.
·1≤N≤105
·2≤M≤109
·1≤Ai≤109
输入
Input is given from Standard Input in the following format: N M A1 A2 … AN
输出
Print the number of the pairs (l,r) that satisfy the conditions. Note that the number may not fit into a 32-bit integer type.
样例输入
3 2 4 1 5
样例输出
3
提示
The sum Al+Al+1+…+Ar for each pair (l,r) is as follows: ·Sum for (1,1): 4 ·Sum for (1,2): 5 ·Sum for (1,3): 10 ·Sum for (2,2): 1 ·Sum for (2,3): 6 ·Sum for (3,3): 5 Among these, three are multiples of 2.
题意：
求能够整除m的区间的个数
开始用了一遍 前缀和 ，再用两个for循环遍历，然后T了
再看模数的取值范围，开不了数组，于是就用map来解决
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math") #pragma GCC optimize("Ofast") #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") #pragma comment(linker, "/stack:200000000") #pragma GCC optimize (2) #pragma G++ optimize (2) #include <bits/stdc++.h> #include <algorithm> #include <map> #include <queue> #include <set> #include <stack> #include <string> #include <vector> using namespace std; #define wuyt main typedef long long ll; #define HEAP(...) priority_queue<__VA_ARGS__ > #define heap(...) priority_queue<__VA_ARGS__,vector<__VA_ARGS__ >,greater<__VA_ARGS__ > > template<class T> inline T min(T &x,const T &y){return x>y?y:x;} template<class T> inline T max(T &x,const T &y){return x<y?y:x;} //#define getchar()(p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++) //char buf[(1 << 21) + 1], *p1 = buf, *p2 = buf; ll read(){ll c = getchar(),Nig = 1,x = 0;while(!isdigit(c) && c!='-')c = getchar(); if(c == '-')Nig = -1,c = getchar(); while(isdigit(c))x = ((x<<1) + (x<<3)) + (c^'0'),c = getchar(); return Nig*x;} #define read read() const ll inf = 1e15; const int maxn = 2e5 + 7; const int mod = 1e9 + 7; #define start int wuyt() #define end return 0 #define N 1005 ///int num[maxn]; ///int sum[maxn]; map<ll,ll>mp; int n; ll m; start{ n=read,m=read; ll num,sum = 0,ans = 0; mp.clear(); mp[0]++; for(int i=1; i<=n;i++) { num=read; sum+=num; sum%=m; ans+=mp[sum]; mp[sum]++; } printf("%lld\n",ans); end; }
