HDU 5776 sum （思维题）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5776

题意：求是否有区间的和是m的倍数。

#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; int sum[100100], cnt[5555]; int main() { int t; scanf("%d", &t); while(t--) { int n, m; scanf("%d %d", &n, &m); int i; sum[0] = 0; memset(cnt, 0, sizeof(cnt)); int flag = 0; for(i = 1; i <= n; i++) { scanf("%d", sum + i); sum[i] = (sum[i] + sum[i - 1]) % m; cnt[sum[i]]++; //两个数模m的值相同，说明中间一部分连续子列可以组成m的倍数 if(cnt[sum[i]] > 1 || sum[i] == 0) { flag = 1; } } puts(flag ? "YES" : "NO"); } return 0; }