2020牛客多校三 F. Fraction Construction Problem (扩展欧几里得)

题意：

题解：扩展欧几里得
d < b, f < b, c > 0, e > 0
分三种情况：
①a、b不互质，求得公因子g，那么一定有$\frac{a+g}{b}-\frac{g}{b}=\frac{a}{b}$ba+g​−bg​=ba​。

（剩余情况$\frac{a}{b}$ba​一定是最简分式）
②b的相异质因子不超过1个，无解。
给出题解证明：

③b的相异质因子超过1。
我们可得$\frac{cf-de}{df}=\frac{a}{b}$dfcf−de​=ba​，可令$df=b$df=b，且$gcd(d,f)=1$gcd(d,f)=1，那么分子之间直接用扩展欧几里得来做就行了。

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#include<queue>
#include<stack>
#include<cmath>
#include<vector>
#include<fstream>
#include<set>
#include<map>
#include<sstream>
#include<iomanip>
#define ll long long
using namespace std;
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
void exgcd(ll a, ll b, ll& d, ll& x, ll& y) {  //d为a、b的最大公约数
    if (!b) {
        d = a;
        x = 1;
        y = 0;
    }
    else {
        exgcd(b, a % b, d, y, x);
        y -= x * (a / b);
    }
}
const int MAXN = 2e4 + 10;
bool notprime[MAXN];
int prime[MAXN / 10];
void getPrime() {
	memset(notprime, false, sizeof(notprime));
	notprime[0] = notprime[1] = true;
	prime[0] = 0;
	for (int i = 2; i < MAXN; i++) {
		if (!notprime[i])prime[++prime[0]] = i;
		for (int j = 1; j <= prime[0] && prime[j] < MAXN / i; j++) {
			notprime[prime[j] * i] = true;
			if (i % prime[j] == 0) break;
		}
	}
}
long long factor[2][2];
int fatCnt;
int getFactors(long long x) {
	fatCnt = 0;
	long long tmp = x;
	for (int i = 1; i < prime[0] && prime[i] <= tmp / prime[i]; i++) {
		factor[fatCnt][1] = 0;
		if (tmp % prime[i] == 0) {
			factor[fatCnt][0] = prime[i];
			while (tmp % prime[i] == 0) {
				factor[fatCnt][1]++;
				tmp /= prime[i];
			}
			fatCnt++;
		}
		if (fatCnt == 1) break;
	}
	if (tmp != 1) {
		factor[fatCnt][0] = tmp;   //存放分解的素数
		factor[fatCnt++][1] = 1;   //存放此素数出现次数
	}
	return fatCnt;   //分解的素数个数（不相同）
}
int t;
ll a, b;
int main() {
	getPrime();
    scanf("%d", &t);
    while (t--) {
        scanf("%lld%lld", &a, &b);
        ll g = gcd(a, b);
        if (g != 1) printf("%lld %lld %lld %lld\n", (a + g) / g, b / g, 1ll, b / g);
        else {
			int cnt = getFactors(b);
			if (cnt <= 1) puts("-1 -1 -1 -1");
			else {
				ll f = 1ll * powl(factor[0][0], factor[0][1]);
				ll d = b / f;
				ll temp, x, y;
				exgcd(f, d, temp, x, y);
				if(x > 0) printf("%lld %lld %lld %lld\n", a * x, d, -a * y, f);
				else printf("%lld %lld %lld %lld\n", a * y, f, -a * x, d);
			}
        }
    }
	return 0;
}