首页 > 代码库 > 100726C

100726C

显而易见,我们要找子串,每次记录前缀和,算出余数,然后通过一个数组保存余数,答案就是加上之前余数的总和,要注意整除的情况

#include<iostream>
#include<cstring>
#include<cstdio>

using namespace std;

int num[1000010];

int main()
{
    int T;scanf("%d",&T);
    while(T--)
    {
        int ans=0,sum=0,n,d;memset(num,0,sizeof(num));
        scanf("%d%d",&d,&n);
        for(int i=1;i<=n;i++) 
        {
            int a;scanf("%d",&a);
            sum=(sum+a)%d; if(sum==0) ans++;
            ans+=num[sum]; num[sum]++;
        }
        printf("%d\n",ans);
    }
    return 0;
}

 

100726C