题目链接
来源：牛客网

题目描述
无奈之下痛定思痛,NE决定也带上自己的10的九次方个小伙伴去gankFF。 FF提前得知了这个消息,这可把FF急坏了.那可是10的九次方个人啊！ 这时FF的小伙伴EN说：“FF莫慌，我这里有3盏BD哥的神灯，上面分别有一个素数，可以让编号被上面的数字整除的人昏睡过去，这样就可以大大削减NE的人数！”（FF所带的10的九次方个人分别被编号为1~10的九次方） FF：“好！”。FF如同找到了救命稻草。但是由于只能削减一部分人数，FF需要召集的人数应该大于等于NE剩下的人数，但是时间紧急，FF算不出来了，你能告诉FF至少要准备多少人吗？

输入描述:
第一行包含一个正整数T（T<200）之后的T行每行包含3个正整数,a,b,c(2<=a,b,c<10^6；
a!=b,b!=c,c!=a；
保证a,b,c为素数)分别代表3盏神灯上的数字。
输出描述:
输出T行
每行一个整数,表示FF至少要准备的人数。

示例1
输入
3
2 3 5
5 7 11
13 2 3

输出

266666666
623376624
307692308`

题意：
一个数10的九次方，让我们输入一行数T并在10的九次方的方位内找出不能整除T个数的数有多少个；

解题思路：

根据容斥定理的推论就可以得出：（注　：|A| 意思代表A集合中元素的个数）
｜ＡＵＢＵＣ｜＝| A | + | B | + | C | - | A ∩ B | - |A ∩ C| - | B ∩ C | + | A ∩ B ∩ C |；

做题目步骤：

1.时间复杂度考虑
时间少于O（10^9）,但枚举会超时。

2.分析题目
目标：1-10^9中，不能被a,b,c 整除的最少个数

容斥原理不会。太菜了

分解问题：

分而治之，或者反其道而行之。

这题我们先反着思考。

将问题变成：1-10^9 能a,b,c被整除的最多的个数。

在集合10^9方里，除去被a,b,c整除的数。

分析：

1.细节 a!=b,b!=c,c!=a；并且都大于2

3.选择算法，或者解决问题的知识点。

通过分析，在已经学习的知识里，马上就可以想到容斥原理。

4.考虑优化，数组大小，数据类型
ll

总结提升：
1.对于容斥原理使用掌握的不够：
2.需要扩展知识面。

关于 容斥原理知识：
1.简单的排列问题
2.方程整数解问题
3.求指定区间内与n互素的数的个数：
4.求在给定区间内，能被给定集合至少一个数整除的数个数
5.能满足一定数目匹配的字符串的个数问题
6.路径的数目问题
7.错排问题
推荐博客：记录

# include<iostream>
# include<cstdio>
# include<cstring>
using namespace std;
typedef long long ll;
const ll maxn=1e9;
int main()
{
   
    int T;
    scanf("%d",&T);
    while(T--)
    {
   
        ll a,b,c;
        ll ans;
        scanf("%lld%lld%lld",&a,&b,&c);
        ans=maxn/a+maxn/b+maxn/c-maxn/(a*b)-maxn/(a*c)-maxn/(b*c)+maxn/(a*b*c); //容斥定理；
        printf("%lld\n",maxn-ans);
    }
    return 0;
 }