Input
第一行一个整数 T 代表case数。
每个case第一行是两个整数 n（1≤ n≤ 100000）, p( 1≤p≤1000000),第二行是n个整数
1≤a(k) ≤10000( 1≤k≤n).
Output
每个case输出一行，存在连续个a，这些a的和能被p整除就输出“Yes”,否则输出“No”.
Sample Input
2
3 5
1 3 2
3 5
4 4 4
Sample Output
Yes
No
一开始直接计算每种情况的值,严重超时
#include<stdio.h>
long int b[100000]=
{0};
int main()
{
long int t,n,p,a;
long int c,i,j;
scanf("%d",&t);
while(t--)
{
c=0;
scanf("%d %d",&n,&p);
for(i=0;i<n;i++)
{
scanf("%d",&a);
a%=p;
if(!c)
{
for(j=i;j>=0;j--)
{
if(!c)
{
b[j]=b[j-1]+a;
if(b[j]%p==0)
c=1;
}
}
b[0]=a;
if(b[0]%p==0)
c=1;
}
}
if(c)
printf("Yes\n");
else
printf("No\n");
}
return 0;
}同学提醒 (sum[i]-sum[j])%p==0和 sum[i]%p==sum[j]%p 相同 顿时开悟
sum[i]为前i项和 sum[j]为前j项和
#include<iostream>
long int b[1000000];
int main()
{
long int t,n,p,a,s;
long int c,i;
scanf("%d",&t);
while(t--)
{
scanf("%ld %ld",&n,&p);
c=0;
s=0;
memset(b,0,p*sizeof(long int));
for(i=0;i<n;i++)
{
scanf("%ld",&a);
s+=a%p;
if(!c)
{
if(b[s%p]==s%p)
c=1;
else
b[s%p]=s%p;
}
}
if(c)
printf("Yes\n");
else
printf("No\n");
}
return 0;
}