HDU 5776 BestCoder Round #85 sum （数学）

HDU 5776 BestCoder Round #85 sum （数学）

sum

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others) Total Submission(s): 557    Accepted Submission(s): 269

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≤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≤100000, 1≤m≤5000). 2.The second line contains n positive integers x (1≤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

Source

​​BestCoder Round #85 ​​

Recommend

wange2014   |   We have carefully selected several similar problems for you:  ​​5780​​​ ​​5779​​​ ​​5778​​​ ​​5777​​​ ​​5775​​

题解： 预处理前缀和，一旦有两个数模m的值相同，说明中间一部分连续子列可以组成m的倍数。另外，利用抽屉原理，我们可以得到，一旦n大于等于m，答案一定是YES 。复杂度 O（n） 。

AC代码：

#includeusing namespace std;int n,m;int a[100010];bool vis[100010];int main(){ int t; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&m); memset(vis,0,sizeof(vis)); int sum=0; vis[0]=1; bool flag=0; for(int i=1;i <= n;i++) { scanf("%d",&a[i]); sum=(sum+a[i])%m; if(vis[sum]) { flag=1; } //如果有两个余数相同，那这相加的数中一定有可模 m 的 vis[sum] = 1; } puts(flag ?"YES" : "NO"); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。