P8255 [NOI Online 2022 入门组] 数学游戏

注：妙哉，此题可以理解为数学题。

思路

由题易得：

\[\notag z=d_x\times d_y\times \gcd(x,y)^3\\ x=d_x\times \gcd(x,y)\\ y=d_y\times \gcd(x,y)\\ \]

令\(d=\gcd(x,y)\)，此时有\(d_x\bot d_y\)

可以得到只要证明出\(d\)的表达式，即可解题。

\[\notag c=z/x=d_y\times d^2\\ \gcd(c,x^2)=\gcd(d_y\times d^2,d_x^2\times d^2) =d^2\times\gcd(d_y,d_x^2)=d^2\\ 即d^2=gcd(c,x^2)\\ 即d=\sqrt{(gcd(c,x^2))} \]

所以无解的情况有以下两种：

• \(x\nmid z\)
• \(d^2\)解出来不是平方数

题目大概是这样，但这里可能会有一个疑惑：

• 为什么不可以直接\(d=\gcd(c,x)=\gcd(d_y\times d^2,d_x\times d)\)，反正\(d_x\bot d_y\)？

  其实这是显然的，因为不保证\(d_x\bot d\)，所以结果不会为\(d\)。

总结

当遇到像\(c=d_y\times d^2,x=d_x\times d\)时，不妨将\(x\)平方一下，使目标数的次数相同。

CDOE

#include
#define ll long long
using namespace std;
const ll maxn =1e8+32;

inline ll read_int(){
    ll a=0,f=1,g=getchar();
    while(g<'0'||g>'9'){if(g=='-') f=-1;g=getchar();}
    while(g>='0'&&g<='9') a=a*10+g-'0',g=getchar();
    return a*f;
}

inline void write(ll a,ll b){
    if(a<0) a=-a,putchar('-');
    ll lin[40],cnt=0;
    while(a) lin[++cnt]=a%10,a/=10;
    if(!cnt) cnt++,lin[cnt]=0;
    while(cnt) putchar(lin[cnt]+'0'),cnt--;
    if(b) putchar('\n');
}

inline ll gcd(ll a,ll b) {return b==0 ? a : gcd(b,a%b);}

inline void read(){
	ll x=read_int(),z=read_int();
	if(z%x) {write(-1,1);return;}
	z/=x;
	ll G=gcd(z,x*x);
	ll lin=sqrt(G);
	if(lin*lin!=G) {write(-1,1);return;}
	write(z/lin,1);
}

int main (){
	ll t=read_int();
	while(t--) read();
}