牛客练习赛43 Tachibana Kanade Loves Game (简单容斥)

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

题目描述

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

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

在游戏中，立华奏拥有 k 点血量，而她的对手拥有 q 点血量。当她的血量变为 0 时，游戏便结束了；同理，如果对方的血量变为 0，立华奏就获胜了。在立华奏手中，有 n 种武器，编号分别为1,2,⋯,n1,2,⋯,n，每一种武器在使用后，都能让对方受到 1 点伤害，且此后不得再次使用这个武器。同时，对方拥有m−1m−1 种反击魔咒，编号分别为 2,3,4,⋯,m2,3,4,⋯,m（如果 m = 1，则可认为此时不具有反击魔咒）。如果立华奏在使用第 i 种武器攻击对方时，对方恰好有编号为 j 的魔咒，且j∣ij∣i， 那么立华奏会受到 1 点伤害（注意此时，攻击仍然是有效的，即对方的血量仍然会减少 1），同时对方也可以再次使用这个反击魔咒。

由于立华奏是个萌新，因此对方保证不会主动攻击立华奏 。

现在，立华奏想要知道，自己是否存在一种攻击方案，使得自己取得胜利。

输入描述:

输入包含多组数据。

输入的第一行包含一个整数 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

思路:我们先来求出n个武器里哪个可以打出1点伤害 且不会伤害自己 这个伤害其实就是n中不是[2，m]中数的倍数的数的个数，所以我们可以二进制枚举 然后容斥算出个数

当然这里算出的是[2,m]的倍数的个数 所以要用n减去这个个数 再做最后的判断即可

#include <cstdio>
#include <map>
#include <iostream>
#include<cstring>
#include<bits/stdc++.h>
#define ll long long int
#define M 6
using namespace std;
inline ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
inline ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
int moth[]={,,,,,,,,,,,,};
int dir[][]={, ,, ,-, ,,-};
int dirs[][]={, ,, ,-, ,,-, -,- ,-, ,,- ,,};
const int inf=0x3f3f3f3f;
const ll mod=1e9+;
ll a[]={,,,,,,,};
int tot;
int main(){
    ios::sync_with_stdio(false);
    int t;
    cin>>t;
    while(t--){
        ll k,q,n; int m;
        cin>>k>>q>>n>>m;
        tot=;
        for(int i=;i<;i++){
            if(m>=a[i])
                ++tot;
            else break;
        }
        ll ans=;
        for(int i=;i<(<<tot);i++){ //枚举素数
            ll temp=;
            int cnt=;
            for(int j=;j<tot;j++)
                if(i&(<<j)){
                    cnt++;
                    temp*=a[j];
                }
            if(cnt&) ans+=n/temp; //奇加偶减
            else ans-=n/temp;
        }
        ans=n-ans;
        if(k&&ans+k>q){
            puts("Yes");
        }else{
            puts("QAQ");
        }
    }
}