容斥原理求非约数

容斥原理求非约数

问题:给出一个数n,求1到n中,有多少个数不是2 5 11 13的倍数。

根据容斥原理,应该先求出n个数中分别是2、5、11、13的数的倍数的个数。
再处理重叠的数。

#include<iostream>
using namespace std;

int main()
{
    long long n,sum=0;
    long long a,b,c,d,ab,ac,ad,bc,bd,cd,abc,acd,bcd,abd,abcd;
    while(cin>>n)
    {
        //2,5,11,13的倍数
        a=n/2;
        b=n/5;
        c=n/11;
        d=n/13;
        //两数的倍数
        ab=n/10;
        ac=n/22;
        ad=n/26;
        bc=n/55;
        bd=n/65;
        cd=n/143;
        //三数的倍数
        abc=n/110;
        abd=n/130;
        acd=n/286;
        bcd=n/715;
        //四数的倍数
        abcd=n/1430;
        sum=a+b+c+d-ab-ac-ad-bc-bd-cd+abc+abd+acd+bcd-abcd;  //不可写成乘法形式
        cout<<n-sum<<endl;       //因为上面倍数不一定整除
    }
    return 0;
}

数论好菜啊

... ... ...