显而易见，我们要找子串，每次记录前缀和，算出余数，然后通过一个数组保存余数，答案就是加上之前余数的总和，要注意整除的情况
#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; }
原文：http://www.cnblogs.com/19992147orz/p/6021057.html