容斥原理 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; } }