线段树70pts求调

#include<bits/stdc++.h>
#define int long long
using namespace std;
#define N 100005
#define ls rt<<1
#define rs rt<<1|1
const int awa=-114514;
struct node{
    int l,r,mul;
}tree[N<<2];
int n,k,ans,a[N];
void push_up(int rt){ 
    tree[rt].mul=(tree[ls].mul*tree[rs].mul)%k;
    return;
}
void build(int rt,int x,int y){ 
    tree[rt].l=x,tree[rt].r=y;
    if(x==y){
        tree[rt].mul=a[x]%k;
        return;
    }
    int mid=(x+y)>>1;
    build(ls,x,mid);
    build(rs,mid+1,y);
    push_up(rt);
    return;
}
int query(int rt,int x,int y){
	if(x<=tree[rt].l&&y>=tree[rt].r) return tree[rt].mul%k;
	int ret=0,mid=(tree[rt].l+tree[rt].r)>>1;
	if(x<=mid) ret=query(ls,x,y);
	if(y>mid) ret=query(rs,x,y);
	return ret;
}
signed main() {
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin>>n>>k;
    for(int i=1;i<=n;i++) cin>>a[i];
    build(1,1,n);
    for(int i=1;i<=n;i++)
	{
		int l=i,r=n,t=awa;
		while(l<=r)
		{
			int mid=(l+r)/2;
			if(query(1,i,mid)==0){
				t=mid;
				r=mid-1;
			} 
			else l=mid+1;
		}
		if(t!=awa) ans+=n-t+1;
	}
	cout<<ans;
    return 0;
}