牛客练习赛95Dgcd 题解(整除分块)

题目链接

题目思路

其实是一个整除分块的简单题，稍微思考就能写出来

代码

#include
#include
#include
#include
#include
#define fi first
#define se second
#define pii pair
#define debug cout<<"I AM HERE"<>=1;
    }
    return ans;
}
signed main(){
    for(int i=0;i<=3e5;i++){
        a[i]=1;
        inv[i]=qpow(i,mod-2);
    }
    scanf("%d",&n);
    for(int i=1,l,r;i<=n;i++){
        scanf("%d%d",&l,&r);
        l--;
        int nxt;
        for(int j=1;j<=3e5;j=nxt+1){
            if(j>r){
                nxt=3e5;
            }else if(j>l){
                nxt=r/(r/j);
            }else{
                nxt=min(r/(r/j),l/(l/j));
            }
            if(r/j==l/j){
                b[j]++;
                b[nxt+1]--;
            }else{
                a[j]=a[j]*(r/j-l/j)%mod;
                a[nxt+1]=a[nxt+1]*inv[(r/j-l/j)]%mod;
            }
        }
    }
    ll pr=0;
    for(int i=1;i<=3e5;i++){
        a[i]=a[i-1]*a[i]%mod;
        b[i]+=b[i-1];
        if(b[i]<=0){
            pr=(pr+a[i])%mod;
        }
    }
    printf("%lld\n",pr);
    return 0;
}