【HDU】5776 - sum（数论 & 思维）

点击打开题目

sum

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

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

题意：问是否有一个子序列的和是k的倍数。

题解：用一个sum数组存从1到当前的和并取余，如果某个余数出现两次或余数为 0 为真，那么输出YES，否则输出NO。

代码如下：

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define INF 0x3f3f3f3f
#define CLR(a,b) memset(a,b,sizeof(a))
int main()
{
    int u;
    int n,k;
    int ant[5000+11];
    int sum[100000+11];
    int t;
    scanf ("%d",&u);
    while (u--)
    {
        bool ans = false;
        scanf ("%d %d",&n,&k);
        sum[0] = 0;
        CLR(ant,0);
        for (int i = 1 ; i <= n ; i++)
        {
        	scanf ("%d",&t);
			sum[i] = (sum[i-1] + t) % k;
			ant[sum[i]]++;
			if (ant[sum[i]] >= 2)
				ans = true;
		}
		if (ant[0] >= 1)
			ans = true;
        printf (ans ? "YES\n" : "NO\n");
    }
    return 0;
}