牛客練習賽43 F 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      

說明

對于第一組樣例，立華奏開始就死掉了，是以答案為QAQ

對于第二組樣例，你隻需要使用所有的不含{2,3,4,5,6,7,8,9}因子的武器即可，顯然在 29999999999999 記憶體在這些武器

對于第三組樣例，立華奏的武器隻有12345678個，但她的對手血量更多，顯然她不可能取勝

對于第四組樣例，你的血量為1，代表你不能使用會觸發反擊魔咒的武器，答案為QAQ

對于第五組樣例，與第四組樣例是相同的      

備注:

1⩽T⩽105,0⩽k⩽1018,0<q⩽1018,0⩽n⩽1018,1⩽m⩽20      

x隻要是2~m中素數的倍數就會使自身減血。是以我們可以把1~n分成2~m中素數的個數份集合，然後求集合的并集就是會造成減血的武器數目。

比如m=5 則2~m中素數為 2 3 5 則可以得到三個集合n/2 n/3 n/5隻要利用容斥原理求出三個集合的并集即可。

使自身減血的武器個數為 n-n/2-n/3n-n/5+n/6+n/10+n/15-n/30

可以用dfs來求解改表達式

//#include<bits/stdc++.h>
#include <set>
#include <map>
#include <cmath>
#include <queue>
#include <stack>
#include <time.h>
#include <vector>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <functional>
#define sdddd(x,y,z,k) scanf("%d%d%d%d", &x, &y, &z, &k)
#define sddd(x,y,z) scanf("%d%d%d", &x, &y, &z)
#define sdd(x,y) scanf("%d%d", &x, &y)
#define sd(x) scanf("%d", &x)
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=a;i>=b;i--)
//#define mp make_pair
#define pb push_back
#define ms(x, y) memset(x, y, sizeof x)
#define MOD 10000
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn = 50000050;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
//typedef vector<ll> vec;
//typedef vector<vec> mat;
template <class T>
inline bool scan_d(T &ret) {
    char c; int sgn;
    if (c = getchar(), c == EOF) return 0;
    while (c != '-' && (c<'0' || c>'9')) c = getchar();
    sgn = (c == '-') ? -1 : 1;
    ret = (c == '-') ? 0 : (c - '0');
    while (c = getchar(), c >= '0'&&c <= '9') ret = ret * 10 + (c - '0');
    ret *= sgn;
    return 1;
}
int arr[30] = {0,0,1,2,2,3,3,4,4,4,4,5,5,6,6,6,6,7,7,8,8};
int prime[20] = {0,1,2,3,5,7,11,13,17,19,23};
ll n, m, k, q, t;
ll res;
void dfs(int i, int cnt, ll tot){
    if(prime[i+1] > m){
        if(cnt%2){
            res -= n/tot;
        }
        else{
            res += n/tot;
        }
        return;
    }
    dfs(i+1, cnt+1, tot*prime[i+1]);
    dfs(i+1, cnt, tot);
}

int main()
{
    //std::ios::sync_with_stdio(false);
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
    scan_d(t);
    while(t--){
        res = 0;
        scan_d(k); scan_d(q); scan_d(n); scan_d(m);
        if(k == 0){
            puts("QAQ");
            continue;
        }
        else{
            dfs(1,0,1);
            //cout << res << "\n";
            if(res+k > q)
                puts("Yes");
            else
                puts("QAQ");
        }
    }
    return 0;
}