组合数学-容斥原理（持续更新）

ゞ浴缸里的玫瑰 2023-06-03 13:52 90阅读 0赞

容斥原理：在计数时，必须注意无一重复，无一遗漏。为了使重叠部分不被重复计算，人们研究出一种新的计数方法，这种方法的基本思想是：先不考虑重叠的情况，把包含于某内容中的所有对象的数目先计算出来，然后再把计数时重复计算的数目排斥出去，使得计算的结果既无遗漏又无重复，这种计数的方法称为容斥原理；

AUB=A+B-A∩B n个的容斥，全部+奇数项-偶数项；

HDU：Eddy’s爱好

求1-n内能够组成m^k的个数；

解：需要的知识点：1-n内能用k次方表示的数一共有n^(1/k);（比如25，25内能用2次方表示的一共有5个，1，4，9，16，25）

根据容斥原理，只有素数次方才能满足，非素数的话可以分解成两个比较大的值再用素数的次方；

所以先打表素数，2^60次方就超过1e18，所以只要60以内的素数就可以了；

然后再进行素数的容斥，2\*3\*5\*7>60；所以只要3次，（2，3）（2，3，5）（2，3，5，7）；

所以ans=全部+奇数项-偶数项；

注意每次要减去1，因为每次计算1都会计算进去，我们只需要一次1，所以在结尾的时候再加上1；

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include <bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    ll prime[100];
    int tot=0;
    void getprime(){
        for(int i=2;i<=60;i++){
            int flag=1;
            for(int j=2;j<=sqrt(i);j++){
                if(i%j==0){
                    flag=0;break;
                }
            }
            if(flag)prime[tot++]=i;
        }
    }ll n;
    ll gao(ll x){
        return pow(n,1.0/x)-1;
    }
    int main(){
        getprime();
        while(cin>>n){
            ll ans1=0,ans2=0,ans3=0;
            for(int i=0;i<tot;i++){
                ans1+=gao(prime[i]);
            }
            for(int i=0;i<tot;i++){
                for(int j=i+1;j<tot;j++){
                    ans2+=gao(prime[i]*prime[j]);
                }
            }
            for(int i=0;i<tot;i++){
                for(int j=i+1;j<tot;j++){
                    for(int k=j+1;k<tot;k++){
                        ans3+=gao(prime[i]*prime[j]*prime[k]);
                    }
                }
            }
            cout<<ans1+ans3-ans2+1<<endl;
        }
    
        return 0;
    }

HDU：Visible Trees

题意：求\[1,n\]\[1,m\]区间内互质的对数；

解：对于\[1,n\]的每个数进行素因子分解，对每个1-n的数的因子都跟m容斥；

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include <bits/stdc++.h>
    using namespace std;
    const int maxn=1e5+10;
    typedef long long ll;
    ll a[maxn],b[maxn];
    ll cnt=0;
    void get(ll n){
        ll x=n;
        cnt=0;
        for(int i=2;i<=sqrt(x);i++){
            if(x%i==0){
                a[cnt++]=i;
                while(x%i==0)x/=i;
            }
        }
        if(x>1)a[cnt++]=x;
    }
    ll gao(ll n){
        ll sum=n;
        int tot=0,t;
        b[tot++]=1;
        for(int i=0;i<cnt;i++){
            t=tot;
            for(int j=0;j<tot;j++){
                b[t++]=a[i]*b[j]*(-1);//容斥
                sum+=n/b[t-1];
            }
            tot=t;
        }
        return sum;
    }
    int main(){
        ios::sync_with_stdio(false);
        int T;
        cin>>T;
        while(T--){
            memset(a,0,sizeof(a));
            memset(b,0,sizeof(b));
            int n,m;
            cin>>n>>m;
            ll ans=0;
            for(int i=1;i<=n;i++){
                get(i);
                ans+=gao(m);
            }
            cout<<ans<<endl;
        }
    
    
        return 0;
    }

HDU：How many integers can you find

题意：求1-N内是含有ai的因子的个数

解：对于每个ai跑一遍dfs，每遍dfs都从本身跑到尾；

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include <bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int maxn=110;
    ll a[maxn];
    ll b[maxn];
    int m;
    ll n;
    ll _lcm(ll x,ll y){
        return x*y/__gcd(x,y);
    }
    ll dfs(int tot,int now,ll lcm,int op){
        ll res=0;
        if(op>tot)return 0;
        lcm=_lcm(a[now],lcm);
        if(op%2)res+=(n-1)/lcm;
        else res-=(n-1)/lcm;
        for(int i=now+1;i<tot;i++){
            res+=dfs(tot,i,lcm,op+1);
        }
        return res;
    }
    int main(){
        ios::sync_with_stdio(false);
        while(cin>>n>>m){
            int tot=0,x;
            for(int i=1;i<=m;i++){
                cin>>x;
                if(x&&x<n)a[tot++]=x;
            }
            ll ans=0;
            for(int i=0;i<tot;i++){
                ans+=dfs(tot,i,1,1);
            }
            cout<<ans<<endl;
        }
    
    
        return 0;
    }

HDU:3208

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include <bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const double eps=1e-18;
    const ll inf=1e18+500;
    const ll INF=1LL<<31;
    ll sum[80];
    ll ksm(ll x,ll y){
        ll ans=1;
        while(y){
            if(y&1){
                if(ans>1.0*inf/x)return -1;
                ans*=x;
            }
            y>>=1;
            if(x>1.0*inf/x&&y>0)return -1;
            x*=x;
        }
        return ans;
    }
    ll find(ll x,ll k){
          //pow精度不够自己来凑
        ll r=(ll)pow(x,1.0/k);
        ll t,p;
        p=ksm(r,k);
        if(p==x)return r;
        if(p>x||p==-1)r--;
        else{
            t=ksm(r+1,k);
            if(t!=-1&&t<=x)r++;
        }
        return r;
    }
    ll gao(ll n){
        //if(n<=3)return n;
        sum[1]=n;
        int maxx=0;
        for(int i=2;i<64;i++){
            sum[i]=find(n,1LL*i);
            sum[i]--;//减去1
            if(sum[i]==0){
                maxx=i;
                break;
            }
        }
        for(int i=maxx;i>=2;i--){
            for(int j=1;j<i;j++){
                if(i%j==0)sum[j]-=sum[i];
            }
        }
        ll res=0;
        for(int i=1;i<=maxx;i++){
            res+=sum[i]*i;
        }
        return res;
    }
    int main(){
        ll a,b;
        while(cin>>a>>b){
            if(a==0&&b==0)break;
            ll ans=gao(b)-gao(a-1);
            cout<<ans<<endl;
        }
        return 0;
    }

[ ][Link 1]

转载于:https://www.cnblogs.com/lin1874/p/11364608.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20230601/a9190af57818468e8e05a052d2a26c2d.png
[Link 1]: https://vjudge.net/problem/20095/origin