51nod 1248 2 3 5 7 的倍数

题目描述

给出一个数N，求1至N中，有多少个数不是2 3 5 7的倍数。 例如N = 10，只有1不是2 3 5 7的倍数。

输入

输入1个数N(1 <= N <= 10^18)。

输出

输出不是2 3 5 7的倍数的数共有多少。

INPUT : 10
OUTPUT : 1

算法一

容斥原理

P(A U B U C)= P(A) + P(B) + P(C) - P(AB) - P(AC) - P(BC) + P(ABC)
结论 n 个事件并集的可能性 为
P(A U B U C ··· U Z) = P(奇数个事件同时发生的和) - P(偶数个事件同时发生的和)
↑ ↑ ↑ ↑ ↑
↑ ↑ ↑ ↑ ↑ 共有n个（不失一般性）

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>

using namespace std;

typedef long long LL;

int main() 
{
    /*
    2 3 5 7 
    2*3 2*5 2*7 3*5 3*7 5*7
    2*3*5 2*3*7 2*5*7 3*5*7
    2*3*5*7
    */
    LL a;
    scanf("%lld" , &a);
    LL res = 0;//12 + 8 + 4 + 3 - 2 - 2 - 1 - 1 - 1     
    res = a / 2 + a / 3 + a / 5 + a / 7 + a / 30 + a / 42 + a / 70 + a / 105 - (a / 6 + a / 10 + a / 14 + a / 15 + a / 21 + a / 35 + a / 210);
    printf("%lld" , a - res);
    return 0;
}

算法二

找规律

通过打表发现 每 210 个数字里面都有48个是不能被组合出来的

打表代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <cmath>

using namespace std;

typedef long long LL;

int main() 
{
    int res1 = 0 , res2 = 0 , res = 0;
    for(LL i = 1 ; i <= 840 ; i ++ ) {//将840改为210的倍数即可 发现每增加210 都会增加48
        if(i % 2 == 0 || i % 3 == 0 || i % 5 == 0 || i % 7 == 0) continue;
        else cout << i << endl , res ++ ;
    }
    cout << endl << res;
    return 0;
}

AC 代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <cmath>

using namespace std;

typedef long long LL;

int main() 
{
    LL a;
    cin >> a ;
    LL res = 0;
    res = a / 210 * 48;
    a -= a / 210  * 210;
    for(LL i = 1 ; i <= a ; ++ i) {
        if(i % 2 == 0 || i % 3 == 0 || i % 5 == 0 || i % 7 == 0) continue;
        else  res ++ ;
    }
    cout << res;
}