容斥原理+二进制枚举

容斥原理

n范围内不与x互质的数=Σ(n/(任意1个质因数)) - Σ(n/(任意2个质因数的乘积)) + Σ(n/(任意3个质因数的乘积)) - Σ(n/(任意4个质因数的乘积))……
简单来说就是奇加偶减
那么怎么去算呢 我们可以用二进制的每一位去算个数
比如质因数有2 3 5 那么我们可以用三位二进制来表示有没选这三个数
001 说明是2的倍数
010 说明是3的倍数
011 说明既是2的倍数又是3的倍数 也就是6的倍数
100 说明是5的倍数
101 说明是10的倍数
111 说明是15的倍数
又因为不需要去考虑000的情况 也就是空集的情况 所有一共有2^3-1种
那么怎么枚举呢 可以用位运算去判断每一位是不是1 用一个变量num记录1的个数 如果是奇数 根据容斥原理 我们就加上这个数 偶数就减去即可
并去计算n内有多少个数字是这个数的倍数
比如010 是3的倍数 如果是n=17 17/3=5 说明范围内有5个是3的倍数 又因为只有奇数(1)个质因数 所以要加上5 注意这里算的结果是与x不互质的数 最后总数减去不互质的数自然就是互质的数了

下面给出一个求n范围内与2，3，5互质的数的个数的示例

#include<bits/stdc++.h>
using namespace std;
int a[]= {2,3,5};
int main()
{
    int n;
    while(cin>>n)
    {
        int len=3,up=1<<3,sum=0;
        for(int i=1; i<up; i++)
        {
            int ans=1,num=0;
            for(int j=0; j<len; j++)
            {
                if((i>>j)&1)
                {
                    num++;
                    ans*=a[j];
                }
            }
            if(num&1)
                sum+=n/ans;
            else
                sum-=n/ans;
        }
        cout<<n-sum<<endl;

    }
}