HDU

同余(思维)

题意:输入 n m, 下一行输入 n 个数 ;问:在该序列中是否存在连续的子序列的和可以被 m 整除?

思路:计算前缀和,并且每个前缀和对 m 取余,记录结果。若存在这样一种序列,那么取余的结果必定出现第二次,也就是说,当前取余结果若出现过,那么在出现过的那个位置到现在这个位置的区间和为 m 的整数倍。

【 (d+m ) %k=d 】 ==【 d%k =d 】

撸代码:

 1#include<stdio.h>
2#include<string.h>
3int main()
4
{
5    int t;
6    scanf("%d",&t);
7    int n,m;
8    bool book[5010];
9    while(t--)
10    {
11        memset(book,0,sizeof(book));
12        scanf("%d%d",&n,&m);
13        int x;
14        int sum=0;
15        bool flag=0;
16        for(int i=1;i<=n;i++)
17        {
18            scanf("%d",&x);
19            sum+=x;
20            sum=sum%m;
21            if(book[sum]||sum==0)
22                flag=1;
23            else
24                book[sum]=1;
25            //printf("sum=%d ",sum);
26        }
27        if(flag)
28            printf("YES ");
29        else
30            printf("NO ");
31    }
32    return 0;
33}
原文地址:https://www.cnblogs.com/HappyKnockOnCode/p/12864915.html