2020牛客暑期多校第三场 F-Fractio Construction Problem(扩展欧几里得）

题目戳这里
题意：

分情况讨论下：
1.设g=gcd（a,b），若g > 1,即不为最简分式，此时直接令d = b/g,c = a+b,e = f = 1,即可因为此时构造是满足d < b并且f < b的
2.g = 1,此时分式为最简分式，但如果 b 不能分解出两个不一样的质因子，此时就无法完成构造，直接输出-1
3.g = 1,但是此时b有两个不同质因数，通分后分子上即可变为cf-de = agcd(f,d),即便未解方程fx-dy = agcd（f,d），可知变为扩展欧几里德问题。
最后别忘了我们求得结果再乘上a才是对应于我们这一问题的解

代码：

#include <bits/stdc++.h>using namespace std;
typedef long long ll;
const int MAXN = 2e6+7;
int prime[MAXN],fac[MAXN],cnt;ll gcd(ll a,ll b){if(a < b) swap(a,b);ll r;while(a%b != 0){r = a % b;a = b;b = r;}return b;
}ll exgcd(ll a,ll b,ll &x,ll &y){if(!b){x = 1, y = 0;return a;}ll g = exgcd(b,a%b,y,x);y -= (a/b)*x;return g;
}void euler(){//欧拉筛打出当前的数的质因数是多少int t;fac[1] = 1;for(int i = 2;i < MAXN;i ++){if(!fac[i]){prime[++cnt] = i;fac[i] = i;}for(int j = 1;(t = i*prime[j]) < MAXN;j ++){fac[t] = prime[j];if(i % prime[j] == 0) break;}}
}int main()
{ll a,b,c,d,e,f;int t;euler();scanf("%d",&t);while(t--){scanf("%lld%lld",&a,&b);ll g = gcd(a,b);if(g > 1){a /= g,b /= g;d = b,c = b + a,e = f = 1ll;printf("%lld %lld %lld %lld\n",c,d,e,f);}else{d = 1,f = b;while(fac[b] != 1 && f%fac[b] == 0){//有多个质因子的情况d *= fac[b];f /= fac[b];}if(b == d || f == 1){//不能进行分解的情况puts("-1 -1 -1 -1");}else{exgcd(f,d,c,e);e = -e;while(e <= 0 ||c <= 0){e += f;c += d;}e *= a;c *= a;printf("%lld %lld %lld %lld\n",c,d,e,f);}}}return 0;
}