出题人题解 | #Tachibana Kanade Loves Game#

原题解链接：https://ac.nowcoder.com/discuss/173818

简单的数学题。

首先，你需要注意到题面种“若存在$j\mid ij\; \backslash mid\; i$，则会使的你的血量减少 $11$”这句话的含义，是“如果存在，那么血量减$11$”，因此无论有多少个$jj$ 满足$j\mid ij\; \backslash mid\; i$ ，你的血量都只会减少$11$

考虑$k=0k=0$时，你开局就死了，因此答案一定为$QAQQAQ$

考虑$k=1k=1$，即你不能选择任何会触发反击魔咒的武器，即你能够选择的数，不是$[2,m][2,m]$中任何一个数的倍数。当 $m=1m\; =\; 1$ 时，注意到我们不需要考虑任何情形。否则，考虑任意一个数$d\in [2,m]d\backslash in\; [2,m]$，若其不为素数，则其一定有真素因子$pp$，若$p\nmid xp\; \backslash nmid\; x$，则$d\nmid xd\; \backslash nmid\; x$，因此我们只需要考虑$[2,m][2,m]$的全体素数构成的集合，不妨记其为${\mathbb{P}}_m\backslash mathbb\; P\_m$ ，则显然答案为： ${\sum }_{i=1}^n{\prod }_{j\in {\mathbb{P}}_m}[j\nmid i]\backslash sum^n\_\{i=1\}\; \backslash prod\_\{j\backslash in\; \backslash mathbb\; P\_m\}\; [j\; \backslash nmid\; i]$然而这个式子难以处理，因此我们重新考虑后面的谓词表达式。记然而这个式子难以处理，因此我们重新考虑后面的谓词表达式。记$P={\prod }_{j\in {\mathbb{P}}_m}jP=\backslash prod\_\{j\backslash in\; \backslash mathbb\; P\_m\}\; j$，那么如果，那么如果$\mathrm{\forall }j\in {\mathbb{P}}_m\backslash forall\; j\; \backslash in\; \backslash mathbb\; P\_m$，都有，都有$j\nmid xj\; \backslash nmid\; x$，那么一定有，那么一定有$(P,x)=1(P,\; x)=1$，反之亦然。

结论1：$\mathrm{\forall }j\in {\mathbb{P}}_m\backslash forall\; j\; \backslash in\; \backslash mathbb\; P\_m$,都有$j\nmid xj\; \backslash nmid\; x$的充要条件为$(P,x)=1(P,x)\; =\; 1$

证明：必要性是显然的。

充分性：假设$(P,x)=d\mathrm{\ne }1(P,x)\; =\; d\backslash ne\; 1$，那么一定有$d\mid P,d\mid xd\; \backslash mid\; P,\; d\backslash mid\; x$，设$P=p_1{p}_2\cdots p_{s}P=p\_1p\_2\backslash cdots\; p\_s$，则一定存在$ii$使得$d=p_{i}d\; =\; p\_i$ ，即$p_i\mid xp\_i\; \backslash mid\; x$，与条件矛盾。

因此，我们便可以计算出我们能造成的总伤害$AA$： $A={\sum }_{i=1}^n[(P,i)=1]={\sum }_{i=1}^n{\sum }_{d\mid (P,i)}\mu (d)={\sum }_{d\mid P}\mu (d){\sum }_{i\mid d}1={\sum }_{d\mid P}\lfloor \frac{P}{d}\rfloor \mu (d)A=\backslash sum^n\_\{i=1\}\; [(P,i)\; =\; 1]=\backslash sum^n\_\{i=1\}\; \backslash sum\_\{d\; \backslash mid\; (P,i)\}\; \backslash mu(d)\; =\; \backslash sum\_\{d\backslash mid\; P\}\; \backslash mu(d)\; \backslash sum\_\{i\; \backslash mid\; d\}\; 1\; =\; \backslash sum\_\{d\; \backslash mid\; P\}\; \backslash left\backslash lfloor\backslash frac\; Pd\backslash right\backslash rfloor\; \backslash mu(d)$ 预处理出$[2,m][2,m]$的$\mu (x)\backslash mu(x)$，这个式子就可以通过枚举$PP$的因子计算完成。由于$PP$为$\pi (m)\backslash pi(m)$个不同素数的乘积，因此它的因子个数为$2^{\pi (m)}2^\{\backslash pi(m)\}$。时间复杂度$O(T{2}^{\pi (m)})O(T2^\{\backslash pi(m)\})$，考虑到$\pi (n)\sim \frac{n}{\log n}\backslash pi(n)\; \backslash sim\; \backslash frac\{n\}\{\backslash log\; n\}$可以轻松通过此题

考虑$k>1k\; >\; 1$，我们会发现，我们可以使用$k-1k-1$次会触发反击魔咒的武器，因此总伤害即为$A^{\mathrm{\prime }}=\min \{A+k-1,n\}A\text{'}=\backslash min\; \backslash \{A+k-1,\; n\backslash \}$（要对 $nn$取$minmin$的原因是每种武器只能用$11$次，最多只能造成$nn$ 点伤害）

最后，我们只需要判定$A^{\mathrm{\prime }}⩾qA\text{'}\backslash geqslant\; q$输出$YesYes$，否则输出$NoNo$即可

#include <algorithm>
#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <cmath>
#include <cassert>

constexpr int maxn = 10000000;
constexpr int mod = 20050117;

long long mu[maxn], b[maxn], pri[] = {0, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29}, cnt, d[10005], size, T;
int table[] = {0, 0, 1, 2, 2, 3, 3, 4, 4, 4, 4, 5, 5, 6, 6, 6, 6, 7, 7, 8, 8, 8, 8 };

inline char nc() 
{
    static char buf[1000000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1000000, stdin), p1 == p2) ? EOF : *p1++;
}

inline long long read() 
{
    long long res = 0;
    char ch = nc();
    while (!isdigit(ch)) ch = nc();
    while (isdigit(ch)) res = res * 10 + ch - 48, ch = nc();
    return res;
}

int main() 
{
    d[0] = d[1] = 1;
    mu[0] = mu[1] = 1;
    for (int i = 1; i <= 8; ++i) 
	{
        for (int k = 1; k <= size; ++k) 
		{
            d[k + size] = d[k] * pri[i];
            mu[d[k + size]] = -mu[d[k]];
        }
        d[size = (size << 1) + 1] = pri[i];
        mu[pri[i]] = -1;
    }
    T = read();
    while (T--) 
	{
    	long long k = read(), q = read(), n = read(), m = read();
		if (k == 0) 
		{
			puts("QAQ");
			continue; 
    	}
    	
		long long s, x, y, ans = 0;
        x = 1, y = n, s = m;
        s = table[s];
        --x;
        size = (1 << s) - 1;
        for (int i = 0; i <= size; ++i)
            ans = (ans + mu[d[i]] * (y / d[i] - x / d[i]));
        ans = std::min(n, ans + k - 1);
        if (ans >= q) puts("Yes");
        else puts("QAQ");
    }
    return 0;
}