题目网址

https://cdn.luogu.com.cn/upload/image_hosting/j6e9go3b.png

https://cdn.luogu.com.cn/upload/image_hosting/b7fjsyrv.png

蒟蒻的 Code

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,k,l,r,cnt,Log[N],ST[N][21];
int lcm(int x,int y){
    int l=__gcd(x,y);
    return (x/l)*(y/l);
}
int main(){
    cin>>n>>k>>ST[1][0];
    Log[1]=0;
    for(int i=2;i<=n;i++){
        cin>>ST[i][0];
        Log[i]=Log[i/2]+1;
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=Log[n];j++){
            ST[i][j]=lcm(ST[i][j-1],ST[i+(1<<(j-1))][j-1]);
        }
    }
    for(int i=1;i<=n;i++){
        int l=i,r=n,mid,mi=INT_MAX,ma=INT_MIN;
        while(l<=r){
            mid=(l+r)/2;
            int s=Log[mid-l+1];
            int LCM=lcm(ST[l][s],ST[mid-(1<<s)+1][s]);
            if(LCM<k){
                l=mid+1;
            }else if(LCM==k){
                mi=min(mi,mid);
                r=mid-1;
            }else if(LCM>k){
                r=mid-1;
            }
        }
        l=i,r=n;
        while(l<=r){
            mid=(l+r)/2;
            int s=Log[mid-l+1];
            int LCM=lcm(ST[l][s],ST[mid-(1<<s)+1][s]);
            if(LCM<k){
                l=mid+1;
            }else if(LCM==k){
                ma=max(ma,mid);
                l=mid+1;
            }else if(LCM>k){
                r=mid-1;
            }
        }
        cnt=cnt+(ma-mi+1);
        //l~r:lcm(ST[l][s],ST[r-(1<<s)+1][s])
    }
    cout<<cnt;
    return 0;
}