题目描述
blablabla
样例
blablabla
include [HTML_REMOVED]
include [HTML_REMOVED]
include [HTML_REMOVED]
using namespace std;
const int N=100100;
int n,k;
long long ans=0;
long long a[N],s[N],cut[N],sum[N];//cut数组表示取mo后等于i的个数
int main()
{
cin>>n>>k;
for(int i=1;i<=n;i){
cin>>a[i];
}
for(int i=1;i<=n;i){
s[i]+=s[i-1]+a[i];
sum[i]+=s[i]%k;
ans+=cut[sum[i]];//加上前缀和取模后与之前取模相同的个数
cut[sum[i]]++;//对前缀和取模后榆树出现次数统计
}
cout<<ans+cut[0]<<endl;
// 请在此输入您的代码
return 0;
}
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla