首页 > 代码库 > 2 3 5 7的倍数

2 3 5 7的倍数

2024-08-12 12:14:26   217人阅读

基准时间限制：1 秒 空间限制：131072 KB 分值: 5 难度：1级算法题

 

给出一个数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
 

 

说来惭愧，想了一晚上才终于想通了容斥原理...不过好在终于想通了！

 

正如本题的四个元2 3 5 7，由题意可得{n/2}{n/3}{n/5}{n/7}四个集合，则我们就可以用容斥定理算出四集合并集的大小num，n-num即为所求。

并集的计算方法运用了容斥定理，即四集合总数减去两两相交的个数加三三相交的个数再减四四相交的个数....

 

附AC代码：

 1 #include<iostream> 2 using namespace std; 3  4 int main(){ 5     long long n; 6     cin>>n; 7     long long a,b,c,d,ab,ac,ad,bc,bd,cd,abc,abd,acd,bcd,abcd; 8     long long num=0; 9     a=n/2;10     b=n/3;11     c=n/5;12     d=n/7;13     14     ab=n/6;15     ac=n/10;16     ad=n/14;17     bc=n/15;18     bd=n/21;19     cd=n/35;20     21     abc=n/30;22     abd=n/42;23     bcd=n/105;24     acd=n/70;25     26     abcd=n/210;27     28     num=a+b+c+d-ab-ac-ad-bc-bd-cd+abc+abd+bcd+acd-abcd;29     cout<<n-num<<endl;30     return 0;31 }

 

2 3 5 7的倍数


联系
我们