链接：https://ac.nowcoder.com/acm/contest/5668/F
来源：牛客网

题目描述:

There are t queries. In each query, you are given two positive integers a and b (a,b≤2×1e6).
Please print a line consists of four positive integers c,d,e,f satisfying the following constraints:
• 图片说明
• d < b and f < b
• 1≤c,e≤4×1e12

If there are multiple solutions, you can print anyone.
If there are no solution, please print "-1 -1 -1 -1" in this line.

输入描述：

The first line contains one integer t (1≤t≤1e5) --- the number of test cases.
The only line of each test case contains two integers a and b (1≤a,b≤2×1e6).

输出描述：

For each test case print four integers --- c,d,e,f. If there are no solution, c,d,e,f should all be -1.

solution：

题意：给你两个数a和b，求出满足上述式子的c,d,e,f，不存在都输出-1
1.b=1的时候，不可能出现d,f小于b的情况，输出四个-1
2.b是素数，如果a%b==0，那么就可以构造出a/b+1,1,1,1,四个数
3.如果b是素数，且a%b!=0，说明找不出两个因子，构造出四个数
4.如果a，b互质，我们可以从b中找出互质的两个因子，构造出答案，通过扩展欧几里得算法，求出通解
5.如果a,b不互质，也可以构造出解

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
#define INF 0x3f3f3f3f
ll t,a,b;
int prime[2000005];
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll extend_gcd(ll a,ll b,ll &x,ll &y)
{
    if(a==0&&b==0)return -1;
    if(b==0){x=1;y=0;return a;}
    ll d=extend_gcd(b,a%b,y,x);
    //ll tmp=x;
   // x=y;
    y-=a/b*x;
    return d;
}
int main()
{
    cin>>t;
    for(int i=2;i<=2000000;i++)
        prime[i]=1;
    for(int i=2;i<=2000000;i++)
    {
        if(prime[i])
        {
            for(int j=i*2;j<=2000000;j+=i)
                prime[j]=0;
        }
    }
    while(t--)
    {
        scanf("%lld%lld",&a,&b);
        ll gc=gcd(a,b);
        if(b==1)printf("-1 -1 -1 -1\n");
        else if(prime[b]&&a%b==0)printf("%lld 1 1 1\n",a/b+1);
        else if(prime[b])printf("-1 -1 -1 -1\n");
        else if(gc==1)
        {
            ll c,d,e,f,g=0;
            for(int i=2;i*i<=b;i++)
            {
                if(b%i==0&&gcd(i,b/i)==1)
                {
                    c=i;
                    d=b/i;
                    g=extend_gcd(d,-c,e,f);
                    break;
                }
            }

            if(g==0){printf("-1 -1 -1 -1\n");continue;}
            e*=a;
            f*=a;//cout<<c<<' '<<e<<endl;
            if(d*e<f*c){swap(e,f);swap(d,c);}
            if(f<1||e<1)
                printf("-1 -1 -1 -1\n");
            else
                printf("%lld %lld %lld %lld\n",e,c,f,d);
        }
        else
            printf("%lld %lld 1 %lld\n",1+a/gc,b/gc,b/gc);

    }
    return 0;
}