【杭电】[5776]sum - BoilTask's Blog

问题描述

问题分析

中文题意：
给定一个数列，求是否存在连续子列和为m的倍数，存在输出YES，否则输出NO

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

#include<stdio.h>
#include<string.h>
int flag[10000];
int main() {
    int T;
    scanf("%d",&T);
    while(T--) {
        int n,m;
        scanf("%d %d",&n,&m);
        memset(flag,0,sizeof(flag));
        flag[0]=1;
        bool win=false;
        int sum=0;
        for(int i=0; i<n; i++) {
            int t;
            scanf("%d",&t);
            sum=(sum+t)%m;
            if(flag[sum]==1)
                win=true;
            flag[sum]=1;
        }
        if(win)
            printf("YES\n");
        else
            printf("NO\n");
    }
    return 0;
}