sum
Accepts: 640 Submissions: 1744 Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others) Problem Description
Given a sequence, you’re asked whether there exists a consecutive subsequence whose sum is divisible by m. output YES, otherwise output NO
Input
The first line of the input has an integer T (1≤T≤101 \leq T \leq 101≤T≤10), which represents the number of test cases. For each test case, there are two lines: 1.The first line contains two positive integers n, m (1≤n≤1000001 \leq n \leq 1000001≤n≤100000, 1≤m≤50001 \leq m \leq 50001≤m≤5000). 2.The second line contains n positive integers x (1≤x≤1001 \leq x \leq 1001≤x≤100) according to the sequence.
Output
Output T lines, each line print a YES or NO.
Sample Input
2
3 3
1 2 3
5 7
6 6 6 6 6
Sample Output
YES
NO
/*第一次来打BC,作为大一的大水B,水出一道,已经很高兴了*/
/*用前缀和来遍历每一个连续数列的和*/
#include<iostream>
#include<stdio.h>
#include<string.h>
#define N 100010
using namespace std;
long long a[N],sum[N];
int main()
{
//freopen("in.txt", "r", stdin);
int t;
int n,m;
scanf("%d",&t);
while(t--)
{
memset(sum,,sizeof sum);
memset(a,,sizeof a);
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++)
{
scanf("%d",&a[i]);
sum[i]=sum[i-]+a[i];
}
int flag=;
for(int i=;i<=n;i++)
{
for(int j=i;j<=n;j++)
{
if((sum[j]-sum[i-])%m==)
{
puts("YES");
flag=;
break;
}
}
if(!flag)
break;
}
if(flag)
printf("NO\n");
}
return ;
}Close BestCoder Contest System 2.0Copyright © - HDU ACM