题意：让你求多少个区间 积%k==0
解:考虑双指针
#include<bits/stdc++.h> #define en '\n' #define ll long long using namespace std; const int inf=0x3f3f3f3f; const ll maxn = 1e5+3; const int maxm=maxn<<2; int rd() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x; } ll n,k; int tr[maxm]; void build(int x,int l,int r){ if(l==r){tr[x]=rd()%k;return ;} int mid=(l+r)>>1; build(x<<1,l,mid),build(x<<1|1,mid+1,r); tr[x]=((ll)tr[x<<1]*(tr[x<<1|1]))%k; } int ask(int x,int l,int r,int ql,int qr){ if(ql<=l and r<=qr )return tr[x]; int mid=l+r>>1; int tem=1; if(ql<=mid){tem=((ll)tem*ask(x<<1,l,mid,ql,qr))%k;} if(qr>mid){tem=((ll)tem*ask(x<<1|1,mid+1,r,ql,qr))%k;} return tem; } signed main() { #ifdef local freopen("input2.txt","r",stdin); #endif cin>>n>>k; build(1,1,n); int l=1,r=1; ll ans=0; for(;r<=n;r++){ while(l<r and ask(1,1,n,l+1,r)==0)l+=1; if(ask(1,1,n,l,r)==0)ans+=l; } cout<<ans<<en; return 0; }
