一道比较简单的数学题,但我仍然没做出来。
首先,若 \(x \nmid z\) 则无解。
设 \(d=\gcd(x,y)\),则 \(x=da,y=db\),\(z=x\cdot y\cdot\gcd(x,y)=d^3\cdot ab\),其中 \(\gcd(a,b)=1\)。
最妙的一步:\(\gcd(\frac{z}{x},x^2)=\gcd(d^2\cdot b,d^2\cdot a^2)\)。由于 \(\gcd(a,b)=1\),则 \(\gcd(\frac{z}{x},x^2)=d^2\)。
则若 \(\gcd(\frac{z}{x},x^2)\) 不是平方数则无解,否则 \(d=\sqrt{\gcd(\frac{z}{x},x^2)}\),\(y=\frac{z}{d\cdot x}\)。
代码:
#include <bits/stdc++.h>
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
#define rept(i,n) for(int i=1;i<=n;i++)
#define repe(i,l,r) for(int i=l;i<=r;i++)
#define FOR(i,r,l) for(int i=r;i>=l;i--)
#define pii pair<int,int>
#define mpr make_pair
#define pb push_back
#define fi first
#define se second
#define sz(x) (int)((x).size())
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
int read(){int sum=0,f=1;char c;c=getchar();while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9'){sum=(sum<<1)+(sum<<3)+(c-'0');c=getchar();}return sum*f;}
void out(int x){if(x<0){x=-x;putchar('-');}if(x>=10)out(x/10);putchar(x%10+'0');}
int fast(int a,int b,int P){int res=1;if(P<=0){while(b){if(b&1)res=res*a;a=a*a;b>>=1;}}else{while(b){if(b&1)res=res*a%P;a=a*a%P;b>>=1;}}return res;}
template<typename T> void chmax(T& a,T b){if(a<b)a=b;}
template<typename T> void chmin(T& a,T b){if(a>b)a=b;}
using namespace std;
void solve(){
int x=read(),z=read();
if(z%x){
puts("-1");
return;
}
int tmp=__gcd(z/x,x*x);
int d=sqrt(tmp);
if(d*d!=tmp){
puts("-1");
return;
}
z/=x;
if(z%d==0){
z/=d;
if(z%d==0){
out(z);
puts("");
return;
}
}
puts("-1");
}
signed main(){
int t=read();
while(t--){
solve();
}
return 0;
}