容斥原理解决某个区间[1,n]闭区间与m互质数数量问题

首先贴出代码(闭区间[1,n]范围内和m互质的数）

代码：

int solve(II n,II m){
    vector<II>p;
for(II i=2;i*i<=m;i++){
if(m%i==0){
            p.push_back(i);
while(m%i==0) m/=i;
        }
    }
if(m>1) p.push_back(m); 
    II sz=p.size();
    LL sum=0;
for(II i=1;i<(1<<sz);i++){
        II ct=0;
        LL mul=1;
for(II j=0;j<sz;j++){
if(i&(1<<j)){
                ct++;
                mul*=p[j];
            }
        }
if(ct&1) sum+=n/mul;
else sum-=n/mul;
    }
return n-sum;
}

这里解释一下原理：首先假设m有x个不同的质因子，那么可以组成的因子数就是2^x-1种，然后10^18以内所有的数的质因子个数不会超过15个，所以2^15次方暴力枚举所有情况这个复杂度还是可取的。我们假设p1,p2,p3都是m的质因子，假设当前枚举的因子是p1*p2*p3那么n以内可以整除p1*p2*p3的数量就是n/(p1*p2*p3)，但是这里考虑到一个会重复问题就是拥有奇数个质因数的因子的在n以内可以整除的数量已经包含了偶数个数量，但是偶数个的并不包含奇数个的，所以我们枚举的时候需要奇加偶减，这样我们算出来的ans是n以内和m不互质的数的数量，那么和m互质的数量就是n-ans。

贴上一些可以用这个方法解决的练习题：

HDU1695：这个题好像正解使用什么莫比乌斯反演，题目的意思是求[1,a],[1,b]有多少对数GCD(x,y)==k，但是(x,y)和(y,x)算一对，有一个定理如果GCD(x,y)==k ，则GCD(x/k,y/k)==1那么现在问题转化为求[1,a/k],[1,b/k]以内互质的数有多少对，现在我们要取minn=min(a/k,b/k)，我们可以先求minn的欧拉函数的前缀和，然后再求minn+1到max(a/k,b/k)的数在[1,max(a/k.b/k)]以内所有与它互质的数的数量，然后把所有的加起来就可以了。

代码：

//Author: xiaowuga
#include <bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define MAX INT_MAX
#define mem(s,ch) memset(s,ch,sizeof(s))
const long long N=100000; 
const long long mod=1e9+7; 
typedef long long LL;
typedef int II;
typedef unsigned long long ull;
#define nc cout<<"nc"<<endl
#define endl "\n"
vector<LL>Euler;
void init_Euler(II n){
    Euler.resize(n+1);
    Euler[0]=0;
    Euler[1]=1;
    for(LL i=2;i<n;i++) Euler[i]=i;
    for(LL i=2;i<n;i++){
        if(Euler[i]==i){
            for(LL j=i;j<n;j+=i)
                Euler[j]=Euler[j]/i*(i-1);//先进行除法防止溢出
        }
    }
    for(II i=1;i<n;i++){
        Euler[i]+=Euler[i-1];
    }
}
int solve(II n,II m){
    vector<II>p;
    for(II i=2;i*i<=m;i++){
        if(m%i==0){
            p.push_back(i);
            while(m%i==0) m/=i;
        }
    }
    if(m>1) p.push_back(m); 
    II sz=p.size();
    LL sum=0;
    for(II i=1;i<(1<<sz);i++){
        II ct=0;
        LL mul=1;
        for(II j=0;j<sz;j++){
            if(i&(1<<j)){
                ct++;
                mul*=p[j];
            }
        }
        if(ct&1) sum+=n/mul;
        else sum-=n/mul;
    }
    return n-sum;
}
int main() {
    ios::sync_with_stdio(false);cin.tie(0);
    II a,b,c,d,k;
    II T,ca=0;
    init_Euler(100000+1000);
    cin>>T;
    while(T--){
        cin>>a>>b>>c>>d>>k;
        if(k==0||k>b||k>d){
            cout<<"Case "<<++ca<<": "<<0<<endl;
            continue;
        } 
        if(b>d) swap(b,d);
        b/=k;d/=k;
        LL ans=Euler[b];
        for(II i=b+1;i<=d;i++){
            ans+=solve(b,i);
        }
        cout<<"Case "<<++ca<<": "<<ans<<endl;
    }
    return 0;
}

POJ2773：这个题求第n个与k互质的数。

1.一个简单的思路就是如果[1,k]中有x个与k互质的数，那么[k+1,2*k]中也有x个，每个k个一个循环都会出现x个数与k互质，而且加入y<k且y与k互质，则t*k+y也与k互质。那么我们第一个方法可以暴力算出比k小的数里面所有与k互质的数都是多少复杂度是klog（k），然后看一下n是k第几轮循环里面。然后直接确定这个数多少。

2.二分+验证的思想，首先一个数越大，那么他包含的与k互质的数一定越多对吧？这个性质不就是单调性吗？任何满足单调性的问题我们都可以用二分来解决，所以我们可以用二分，加验证的思想找到和第n个k互质的数是多少

代码：

//Author: xiaowuga
#include<iostream>
#include<vector>
using namespace std;
#define inf 0x3f3f3f3f
#define MAX INT_MAX
#define mem(s,ch) memset(s,ch,sizeof(s))
const long long N=100000; 
const long long mod=1e9+7; 
typedef long long LL;
typedef int II;
typedef unsigned long long ull;
#define nc cout<<"nc"<<endl
#define endl "\n"
LL solve(II r,LL n){
    vector<int>p;
    for(II i=2;i*i<=r;i++){
        if(r%i==0){
            p.push_back(i);
            while(r%i==0) r/=i;
        }
    }
    if(r>1) p.push_back(r);
    LL sum=0;
    for(LL i=1;i<(1<<p.size());i++){
        LL d=1,ct=0;
        for(II j=0;j<p.size();j++){
            if(i&(1<<j)){
                ct++;
                d*=p[j];
            }
        }
        if(ct%2) sum+=n/d;
        else sum-=n/d;
    }
    return n-sum;
}
int main() {
    ios::sync_with_stdio(false);cin.tie(0);
    II n,k;
    while(cin>>n>>k){
        LL l=1,r=inf*2;
        LL ans=1;
        while(l<r){
            LL m=l+(r-l)/2;
            LL t=solve(n,m);
            if(t>=k){
               if(t==k) ans=m;  
               r=m; 
            }
            else{
                l=m+1;
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}