题解 P8255 【[NOI Online 2022 普及组] 数学游戏】

· · 题解

Preface

考场上没想出来，好一道人类智慧题！

Analysis1

较简单的证明。

若 x\nmid z，则一定无解。

令 x=d\times a，y=d\times b，其中 \gcd(a,b)=1。那么有 \gcd(x,y)=d。则 z=x\times y\times \gcd(x,y)=d^3\times a\times b。

我们知道 x 与 z，那么可以求出 \frac{z}{x}=d^2\times b。由于 \gcd(a,b)=1，所以 \gcd(\frac{z}{x},x^2)=\gcd(d^2\times b,d^2\times a^2)=d^2。若 \gcd(\frac{z}{x},x^2) 不是完全平方数，则无解。

将 \gcd(\frac{z}{x},x^2) 开方即可得到 d。那么：

\frac{\frac{z}{x}}{\sqrt{\gcd(\frac{z}{x},x^2)}}=\frac{d^2\times b}{d}=d\times b=y

所以我们有：

y=\frac{\frac{z}{x}}{\sqrt{\gcd(\frac{z}{x},x^2)}}

时间复杂度 O(T\log x)。

Analysis2

更繁琐的证明。

由于 z=x\times y\times \gcd(x,y)，两边同除 x，得：\frac{z}{x}=y\times \gcd(x,y)。若 x\nmid z，则一定无解。

根据唯一分解定理，我们对已知的 x、\frac{z}{x} 与要求的 y 分解质因数：

\begin{cases} \frac{z}{x}=p_1^{a_1}\times p_2^{a_2}\times p_3^{a_3}\times \dots \times p_k^{a_k}\\ x=p_1^{b_1}\times p_2^{b_2}\times p_3^{b_3}\times \dots \times p_k^{b_k}\\ y=p_1^{c_1}\times p_2^{c_2}\times p_3^{c_3}\times \dots \times p_k^{c_k} \end{cases}

由于 \frac{z}{x}=y\times \gcd(x,y)，所以对于任意 i\in[1,k]，有 a_i=c_i+\min(b_i,c_i)。

接下来分两种情况讨论：

合并一下，得到 c_i=a_i-\min(\frac{a_i}{2},b_i)。

两边同时乘以 2 得：2\times c_i=2\times a_i-\min(a_i,2\times b_i)。

最后转化为人话，即：

y^2=\frac{(\frac{z}{x})^2}{\gcd(\frac{z}{x},x^2)}

两边同时开方，得：

y=\frac{\frac{z}{x}}{\sqrt{\gcd(\frac{z}{x},x^2)}}

如果 \gcd(\frac{z}{x},x^2) 不是完全平方数，也是无解。

时间复杂度：O(T\log x)。

Code

Talk is cheap, show me the code.

// And in that light, I find deliverance.
#define int long long
void work(){
    int x,z;read(x,z);
    if(z%x!=0){puts("-1");return;}
    int tmp=__gcd(z/x,x*x);
    int sq=(int)sqrt(tmp);
    if(sq*sq!=tmp) puts("-1");
    else cout<<(z/x)/sq<<endl;
}
signed main(){
    int T;read(T);
    while(T--) work();
}