容斥原理应用

typedef __int64 ll;

ll gao(ll l,ll r,ll n){//[l,r]内与n互素的数字个数 
    vector <ll> v;
    for(ll i=2;i*i<=n;i++){
        if(n%i==0){
            v.push_back(i);
            while(n%i==0)n/=i;
        }
    }
    if(n>1)v.push_back(n);
    int m=v.size();
    ll res=0; 
    for(int i=1;i<(1<<m);i++){
        int cnt=0;
        ll val=1;
        for(int j=0;j<m;j++){
            if(i&(1<<j)){
                cnt++;
                val*=v[j];
            }
        }
        if(cnt&1)res+=r/val-(l-1)/val;
        else res-=r/val-(l-1)/val;
    }
    return r-l+1-res;
}