51 nod 1284 2.3.5.7的倍數

給出一個數N，求1至N中，有多少個數不是2 3 5 7的倍數。 例如N = 10，隻有1不是2 3 5 7的倍數。 Input

輸入1個數N(1 <= N <= 10^18)。      

Output

輸出不是2 3 5 7的倍數的數共有多少。      

Input示例

10      

Output示例

1      

時間超限：

#include <iostream>  

using namespace std;  

int main()

{

long long  i,n,sum;

cin>>n;

sum=n;

for(i=1;i<=n;i++)

{

if(i%2==0 || i%3==0 || i%5==0 || i%7==0)

sum--;

}

cout<<sum;

    return 0;     

} 

AC:

#include <iostream>   

using namespace std; 

typedef long long ll;  

int main(){  

    //離散數學裡面的知識，利用容斥原理（4個集合：A1：2的倍數，A：3的倍數，A3：5的倍數，A4  ：7的倍數）   

    ll a; //A1+A2+A3+A4  

    ll b; //A1A2+A1A3+A1A4+A2A3+A2A4+A3A4  

    ll c; //A1A2A3+A1A2A4+A1A3A4+A2A3A4  

    ll d; //A1A2A3A4   

    ll n,sum,ans;  

    while(cin>>n)

{  

        a=n/2+n/3+n/5+n/7;  //表示是2 3 5 7 的倍數的數個數,裡面包含重複計算

        b=n/6+n/10+n/14+n/15+n/21+n/35;  //任意兩個結合的所有可能情況,裡面包含3個集合相交和4個集合相交 

        c=n/30+n/42+n/70+n/105;  //表示示三個集合相交的情況,包含四個集合相交的情況 

        d=n/210;  //表示四個集合相交 

        //sum為滿足 是2.3.5.7其中一個或多個的倍數  的數；

sum=a-b+c-d; 

        ans=n-sum;  

        cout<<ans<<endl; 

    }  

    return 0;  

} 

AC（便于了解）

#include <iostream>   

using namespace std;  

int main()

{  

    long long n,num,a,b,c,d,ab,ac,ad,bc,bd,cd,abc,abd,bcd,acd,abcd;  

    cin>>n;  

    num=0;  

    a=n/2;  

    b=n/3;  

    c=n/5;  

    d=n/7;  

    ab=n/6;  

    ac=n/10;  

    ad=n/14;  

    bc=n/15;  

    bd=n/21;  

    cd=n/35;  

    abc=n/30;  

    abd=n/42;  

    acd=n/70;  

    bcd=n/105;  

    abcd=n/210;  

    num=a+b+c+d-ab-ac-ad-bc-bd-cd+abc+abd+acd+bcd-abcd;  

    cout<<n-num<<endl;  

    return 0;  

} 

---------------------

容斥原理：

在計數時，必須注意沒有重複，沒有遺漏。

為了使重疊部分不被重複計算，人們研究出一種新的計數方法，

這種方法的基本思想是：先不考慮重疊的情況， 把包含于某内容中的所有對象的數目先計算出來，

然後再把計數時重複計算的數目排斥出去，使得計算的結果既無遺漏又無重複，

這種計數的方法稱為容斥原理。 

要計算幾個集合并集的大小，我們要先将所有單個集合的大小計算出來，然後減去所有兩個集合相交的部分， 

 再加回所有三個集合相交的部分，再減去所有四個集合相交的部分，依此類推，一直計算到所有集合相交的部分。

兩個集合的容斥關系公式：A∪B = A+B - A∩B (∩:重合的部分） 

三個集合的容斥關系公式：A∪B∪C = A+B+C - A∩B - B∩C - C∩A +A∩B∩C 

四個有限集合 ：A∪B∪C∪D=A+B+C+D- A∩B - B∩C - C∩A- A∩D - B∩D - C∩D+A∩B∩C+A∩B∩D +A∩C∩D +B∩C∩D -A∩B∩C∩D

如果被計數的事物有A、B、C三類，那麼，A類和B類和C類元素個數總和= A類元素個數+ B類元素個數+C類元素個數—既是A類又是B類的元素個數—既是A類又是C類的元素個數—既是B類又是C類的元素個數+既是A類又是B類而且是C類的元素個數。（A∪B∪C = A+B+C - A∩B - B∩C - C∩A + A∩B∩C）  [2]   。 例如：一次期末考試，某班有15人數學得滿分，有12人國文得滿分，并且有4人語、數都是滿分，那麼這個班至少有一門得滿分的同學有多少人？ 分析：依題意，被計數的事物有語、數得滿分兩類，“數學得滿分”稱為“A類元素”，“國文得滿分”稱為“B類元素”，“語、數都是滿分”稱為“既是A類又是B類的元素”，“至少有一門得滿分的同學”稱為“A類和B類元素個數”的總和。為15+12-4=23。