2020牛客暑期多校训练营（第三场） F Fraction Construction Problem

有t(1≤t≤10⁵)次查询，每个查询给出两个正整数a,b（a，b≤2×10⁶）。
输出一组满足以下条件的四个正整数c,d,e,f：

如果没有解决方案，输出“ -1 -1 -1 -1”。

进行赛后冷静分析，可以归纳出三种情况，这三种情况只需在代码中依次判断：

情况一：b=1或者b是质数时，一定无解。这种情况很好理解。
情况二：gcd(a,b)!=1时，求出g=gcd(a,b)，一定存在一组解：c=a/g+1，d=b/g，e=1，f=b/g。

情况三：当gcd(a,b)=1，即ab互质时，因为这里b不是质数，可以分成两个相异质因数--d,f，所以要以b=df且d,f互质的条件找到d,f。
寻找2到sqrt(b)的素数，找出第一个被b整除的素数i，然后将f赋值为b/i。

接下来要开始求出c,e。已知b=df，所以根据原方程可得a=c×f−e×d,求解c和e，就能用扩展欧几里得算法来求解c,e。
在求出c和e之后要判断一下正负，通过c和e的正负性判断两个相异质因数分别对应谁。

#include<bits/stdc++.h>
using namespace std;
int gcd(int a,int b)
{
	if(b==0) return a;
	return gcd(b,a%b);
}
long long exgcd(long long a,long long b,long long &x,long long &y)
{
	if(b==0)
	{
		x=1,y=0;
		return a;
	}
	long long s=exgcd(b,a%b,x,y),t=x;
	x=y,y=t-(a/b)*y;
	return s;
}
int main()
{
	int a,b,g,i,j;
	long long c,d,e,f,t,x;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d%d",&a,&b);
		g=gcd(a,b);
        if(g>1)
		{
            printf("%d %d %d %d\n",a/g+1,b/g,1,b/g);
            continue;
        }
        d=f=0;
        for(i=2;i*i<=b;i++)
            if(b%i==0 && gcd(i,b/i)==1)
			{
                d=i,f=b/i;
                break;
            }
        if(d==0 && f==0)
		{
            printf("-1 -1 -1 -1\n");
            continue;
        }
        c=e=0;
        x=exgcd(f,d,c,e);
        c*=a,e*=a;
        if(c>0 && e<0) printf("%lld %lld %lld %lld\n",c,d,-e,f);
        else printf("%lld %lld %lld %lld\n",e,f,-c,d);
	}
}