1e9个兵临城下（容斥原理）

链接：https://ac.nowcoder.com/acm/contest/321/A

来源：牛客网

时间限制：C/C++ 1秒，其他语言2秒

空间限制：C/C++ 32768K，其他语言65536K

64bit IO Format: %lld

题目描述

“FF来训练!”“一定来！”

FF成天到晚咕了NE的训练。这可把NE急坏了。为了拯救ff的知识勺，拥有知识海的NE决定去现实gank一波FF,逼他训练。

可去gank了几波发现ff居然有着成千上万的小伙伴在帮助FF阻拦NE,这几次gank,NE都失败了。无奈之下痛定思痛,NE决定也带上自己的109个小伙伴去gankFF。

FF提前得知了这个消息,这可把FF急坏了.那可是109个人啊！

这时FF的小伙伴EN说：“FF莫慌，我这里有3盏BD哥的神灯，上面分别有一个素数，可以让编号被上面的数字整除的人昏睡过去，这样就可以大大削减NE的人数！”（FF所带的109个人分别被编号为1~109）

FF：“好！”。FF如同找到了救命稻草。但是由于只能削减一部分人数，FF需要召集的人数应该大于等于NE剩下的人数，但是时间紧急，FF算不出来了，你能告诉FF至少要准备多少人吗？

输入描述:

第一行包含一个正整数T（T<200）

之后的T行每行包含3个正整数,a,b,c(2<=a,b,c<106；a!=b,b!=c,c!=a；保证a,b,c为素数)

分别代表3盏神灯上的数字。

输出描述:

输出T行

每行一个整数,表示FF至少要准备的人数。

示例1

输入

复制

输出

复制

题解：

容斥原理

代码：

#include<cstdio>

#include<iostream>

#include<cstring>

#include<algorithm>

using  namespace std;

int main()

{

	int T;

	cin>>T;

	for(int t=0;t<T;t++)

	{

		long long int a,b,c;

		scanf("%lld%lld%lld",&a,&b,&c);

		long long int sum=1000000000;

		long long int a1,a2,a3,a4,a5,a6,a7;

		a1=sum/a;

		a2=sum/b;

		a3=sum/c;

		a4=sum/(a*b);

		a5=sum/(a*c);

		a6=sum/(b*c);

		a7=sum/(a*b*c);

		//cout<<a1+a2+a3-a4-a5-a6+a7<<endl;

		long long int s=sum-(a1+a2+a3-a4-a5-a6+a7);

		cout<<s<<endl;

		//cout<<sum<<endl;

	}

	return 0;

}

巴特西

1e9个兵临城下（容斥原理）

题目描述

输入描述:

输出描述:

输入

输出

最新文章

热门文章