从左到右遍历包含每个选点的所有可能区间
能整除的记作0,不能的记作1
预处理前缀和
如果当前数是0,找到前缀和是s[i]+2的第一个数,这个数所有可能区间是t-i-1
特判,如果最大的前缀和也到不了s[i]+2,这个数所有可能区间是t-i
如果是1,找到前缀和是s[i]+1的
#include <iostream>
using namespace std;
const int N=100010;
int a[N],n,g,s[N];
typedef long long LL;
LL res;
int search_0(int x){
int l=1,r=n;
while(l<r){
int mid=l+r>>1;
if(s[mid]>=x){
r=mid;
}else{
l=mid+1;
}
}
return l;
}
// int search_1(int x){
// int l=1,r=n;
// while(l<r){
// int mid=l+r+1>>1;
// }
// }
int main()
{
cin>>n>>g;
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
a[i]%=g;
if(a[i]>0) a[i]=1;
}
for(int i=1;i<=n;i++){
s[i]=s[i-1]+a[i];
}
for(int i=1;i<=n-1;i++){
if(a[i]==0){
int t=search_0(s[i]+2);
if(s[t]<s[i]+2){
t++;
}
res+=t-i-1;
}else if(a[i]==1){
int t=search_0(s[i]+1);
if(s[t]<s[i]+1){
t++;
}
res+=t-i-1;
}
}
cout<<res;
// 请在此输入您的代码
return 0;
}