牛客网牛客练习赛43 F.Tachibana Kanade Loves Game-容斥(二进制枚举)+读入挂

链接：https://ac.nowcoder.com/acm/contest/548/F
来源：牛客网

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 524288K，其他语言1048576K
64bit IO Format: %lld

题目描述

立华奏是一个天天打比赛的萌新。

省选将至，萌新立华奏深知自己没有希望进入省队，因此开始颓废。她正在颓废一款名为《IODS 9102》的游戏。

在游戏中，立华奏拥有 k 点血量，而她的对手拥有 q 点血量。当她的血量变为 0 时，游戏便结束了；同理，如果对方的血量变为 0，立华奏就获胜了。在立华奏手中，有 n 种武器，编号分别为

输入描述:

输入包含多组数据。

输入的第一行包含一个整数 T，表示数据组数。

接下来 T 行，每行包含四个整数 k, q, n, m，描述一组数据。

输出描述:

输出 T 行，每行描述一组数据的解。如果本组数据中，立华奏存在必胜策略，则输出 Yes，否则输出 QAQ。

你可以认为数据保证不会出现平局的情形。

示例1

输入

复制

5
0 23333 2333333 5
1 1999999999 29999999999999 9
1 998244353998244 12345678 9
1 3 3 4
1 5 6 7

输出

复制

QAQ
Yes
QAQ
QAQ
QAQ

说明

对于第一组样例，立华奏开始就死掉了，因此答案为QAQ

对于第二组样例，你只需要使用所有的不含{2,3,4,5,6,7,8,9}因子的武器即可，显然在 29999999999999 内存在这些武器

对于第三组样例，立华奏的武器只有12345678个，但她的对手血量更多，显然她不可能取胜

对于第四组样例，你的血量为1，代表你不能使用会触发反击魔咒的武器，答案为QAQ

对于第五组样例，与第四组样例是相同的

备注:

这道题就是找区间[1,n]与区间[2,m]中互质的数的个数。其中j|i是j是i的因数。

直接先找出来[2,m]中的素数，然后容斥找不互质的，最后减掉就是互质的。

代码:

 1 //F-读入挂+二进制枚举(容斥)
 2 #include<bits/stdc++.h>
 3 using namespace std;
 4 typedef long long ll;
 5 const int maxn=100+10;
 6 
 7 namespace IO{
 8     char buf[1<<15],*S,*T;
 9     inline char gc(){
10         if (S==T){
11             T=(S=buf)+fread(buf,1,1<<15,stdin);
12             if (S==T)return EOF;
13         }
14         return *S++;
15     }
16     inline int read(){
17         int x; bool f; char c;
18         for(f=0;(c=gc())<'0'||c>'9';f=c=='-');
19         for(x=c^'0';(c=gc())>='0'&&c<='9';x=(x<<3)+(x<<1)+(c^'0'));
20         return f?-x:x;
21     }
22     inline long long readll(){
23         long long x;bool f;char c;
24         for(f=0;(c=gc())<'0'||c>'9';f=c=='-');
25         for(x=c^'0';(c=gc())>='0'&&c<='9';x=(x<<3)+(x<<1)+(c^'0'));
26         return f?-x:x;
27     }
28 }
29 using IO::read;
30 using IO::readll;
31 
32 bitset<maxn>is_prime;
33 int p[maxn],h=0;
34 
35 void Prime(int n)//找素数
36 {
37     is_prime[0]=1;
38     is_prime[1]=1;
39     for(int i=2;i<=n;++i){
40         if(!is_prime[i])
41             p[h++]=i;
42         for(int j=0;j<h&&p[j]*i<=n;++j){
43             is_prime[i*p[j]]=1;
44             if(i%p[j]==0)
45                 break;
46         }
47     }
48 }
49 
50 ll k,q,n,m;
51 
52 ll Calculate()
53 {
54     ll sum=0;int l=h;
55     for(int i=0;i<h;i++){
56         if(p[i]>m){
57             l=i;
58             break;
59         }
60     }
61     for(int i=1;i<(1<<l);i++){//二进制枚举 枚举每一种状态，一共2^n种组合，因为不到2^n，所以小于，然后就是全不选的情况不要，所以从1开始
62         ll mult=1;
63         int bits=0;
64         for(int j=0;j<l;j++){//枚举该状态下的二进制的每一位是选还是不选
65             if(i&(1<<j)){//当前状态的第i位，是否为1，为1要
66                 bits++;
67                 mult*=p[j];
68             }
69         }
70         ll cnt=n/mult;
71         if(bits&1){//加奇减偶
72             sum+=cnt;
73         }
74         else{
75             sum-=cnt;
76         }
77     }
78     return n-sum;
79 }
80 
81 int main()
82 {
83     int t;
84     t=read();
85     Prime(20);
86     while(t--){
87         k=readll();q=readll();n=readll();m=readll();
88         ll x=Calculate();
89         if(k&&k+x>q) printf("Yes
");
90         else printf("QAQ
");
91     }
92 }

牛客网 牛客练习赛43 F.Tachibana Kanade Loves Game-容斥(二进制枚举)+读入挂

题目描述

输入描述:

输出描述:

输入

输出

说明

备注:

牛客网牛客练习赛43 F.Tachibana Kanade Loves Game-容斥(二进制枚举)+读入挂