题目描述

输入格式

第一行一个整数 ，表示有 t 对正整数 x 和 z。

接下来 t 行，每行两个正整数 x 和 z，含义见题目描述。

输出格式

对于每对数字输出一行，如果不存在满足条件的正整数 y，请输出 ?1，否则输出满足条件的最小正整数 y。

数据范围

样例 输入

1
10 240

输出

12

算法: 

数学推导

预备知识(大佬略)

•  gcd

正片

一.考场代码

1. 易知 若gcd(x,y)=d,则x=q*d,y=p*d,且(p,q)=1,所以z=q*d*p*d*d
2. 那么,我发现p*d*d=y*d=z/x,所以d²一定是z/x的约数,所以只要从1~√z/x
   
3. 如果枚举的d是x的约数,且(q,p)=1,则输出

二.正解

　　其实就一行话

　　如果(p,q)=1,则(p²,q)=1,又因x²=(p²*d²),z/x=(q*d²)

　所以d2=gcd(p²*d²,q*d²)

注意:要开long long,还要判z%x==0

C++代码

水过70分

 1 #include
 2 using namespace std;
 3 typedef unsigned long long ull;
 4 int t;
 5 ull gcd(ull a,ull b)
 6 {
 7     if(b==0)return a;
 8     return gcd(b,a%b);
 9 }
10 int main()
11 {
12 //    freopen("math.in","r",stdin);
13 //    freopen("math.out","w",stdout);
14     cin>>t;
15     while(t--)
16     {
17         ull x,z;
18         scanf("%llu%llu",&x,&z);
19         if(z%x!=0)
20         {
21             puts("-1");
22             continue;
23         }
24         if(z==x)
25         {
26             puts("1");
27             continue;
28         }
29         ull d=z/x;
30         ull a=sqrt(z/x)+1;
31         bool flag=false;
32         for(ull i=1;i<=a;i++)
33         {
34             if(d%(i*i)==0)
35             {
36                 ull n=d/i/i;
37                 if(x%i!=0)continue; 
38                 ull m=x/i;
39                 if(gcd(n,m)==1)
40                 {
41 //                    cout<
42                     printf("%llu\n",n*i);
43                     flag=true;
44                     break;
45                 } 
46             }
47         }
48         if(!flag)puts("-1");
49     }
50     return 0;
51 }
52 /*
53 3
54 5 30 
55 4 8 
56 11 11
57 */

100分

 1 #include
 2 using namespace std;
 3 typedef long long ll;
 4 ll gcd(ll x,ll y)
 5 {
 6     if(y==0)return x;
 7     return gcd(y,x%y);
 8 }
 9 int main()
10 {
11     int t;
12     cin>>t;
13     while(t--)
14     {
15         ll x,z;
16         cin>>x>>z;
17         ll d=gcd(x*x,z/x);
18         ll t=sqrt(d);
19         if(z%x!=0)puts("-1");
20         else if(t*t!=d)puts("-1");
21         else if(z%(x*t)==0)cout<endl;
22         else puts("-1");
23     }
24     return 0;
25 }

                                      完结撒花