51nod 1284：2 3 5 7的倍数 容斥原理

1284 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示例

10

Output示例

1

容斥原理的描述如下：

要计算几个集合并集的大小，我们要先将单个集合的大小计算出来，然后减去两个集合相交的部分，再加回三个集合相交的部分，再减去四个集合相交的部分，以此类推，一直计算到所有集合相交的部分。

所以这个题目要求的是不是2 3 5 7的倍数，可以求是2 3 5 7的倍数之后，再减去即可。

这样就会用到容斥原理，先求仅仅只是整除2 3 5 7的数量，再减去整除了它们之间两两的乘积的数量，再加上整除它们三个之间的乘积的数量，再加上整除四个的数量。

而这个数量也很有意思，1到num中整除c的数量正是num/c的值。

所以，代码：

#include <iostream>

#include <algorithm>

#include <cmath>

#include <vector>

#include <string>

#include <cstring>

#pragma warning(disable:4996)

using namespace std;

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

int main()

{

	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;

}

版权声明：本文为博主原创文章，未经博主允许不得转载。