首页 > 代码库 > 2 3 5 7的倍数
2 3 5 7的倍数
基准时间限制：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示例10Output示例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的倍数
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。