2020牛客多校第三场F. Fraction Construction Problem（exgcd）

$F.$
题意： 给定 $a,b$，求出满足 $\frac{c}{d}-\frac{e}{f}=\frac{a}{b}$的任意一组 $c,d,e,f$。
数据范围： $a,b\leq 2\times 10^6$， $1\leq d<b,f<b$，且 $1\leq c,e \leq 4\times 10^{12}$

题解： 通分得到： $\frac{cf-de}{df}=\frac{a}{b}$，那么自然会考虑到分子分母对应相等解决。

• 当 $g=gcd(a,b)>1$，令 $b'=\frac{b}{g},a'=\frac{a}{g}$，此时 $\frac{cf-de}{df}=\frac{a}{b}=\frac{a'}{b'}$
  这时候 $b'<b$，故直接令 $df=b',cf-de=a'$，
  那么可以构造出 $d=b',f=1,c=(a'+b'),e=1$
• $gcd(a,b)=1$，那么此时需要分解 $b$成两个互质的部分 $d,f$，且 $d,f$均不为 $b$，否则判 $-1$
  那么预处理 $2\times10^6$内的质数，并处理出每个数的最小质因子，就可以 $O(\log n)$分解 $b$了。
  分解成功后 $exgcd$即可。
  这里有个技巧，由于是 $cf-de=a$进行 $exgcd$，我们可以变成 $-ed+cf=a$，然后得到 $e$后再取反即可。注意最后的答案必须是正数，且扩大 $a$倍，这也是 $4\times10^{12}$最大范围的原因。
  代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e6 + 10;int pri[N], cnt;
int Mipri[N];
bool st[N];
void xs(int n) {st[0] = st[1] = true;Mipri[1] = 1;for(int i = 2; i <= n; i++) {if(!st[i]) pri[cnt++] = i, Mipri[i] = i;for(int j = 0; j < cnt && 1ll * i * pri[j] <= n; j++) {Mipri[i * pri[j]] = pri[j];st[i * pri[j]] = true;if(i % pri[j] == 0) break;}}
}int gcd(int a, int b) {return b == 0 ? a : gcd(b, a % b);
}void exgcd(ll a, ll b, ll &x, ll &y) {if(!b) {x = 1, y = 0; return ;}exgcd(b, a % b, y, x);y -= a / b * x;
}int main()
{xs(N - 1);int T; scanf("%d", &T);while(T--) {int a, b;scanf("%d%d", &a, &b);int g = gcd(a, b);if(g > 1) {int f = 1, e = 1, d = b / g, c = (a + b) / g;printf("%d %d %d %d\n", c, d, e, f);continue;}ll f = 1, d = b, p = Mipri[b];while(p > 1 && d % p == 0) d /= p, f *= p;if(d == 1) {puts("-1 -1 -1 -1");continue;}ll c, e;exgcd(d, f, e, c);e = -e;if(e <= 0 || c <= 0) {ll e1 = (e % f + f) % f;ll c1 = (c % d + d) % d;ll cnt = max(0ll, max((e1 - e) / f, (c1 - c) / d));e += f * cnt, c += d * cnt;}e *= a, c *= a;printf("%lld %lld %lld %lld\n", c, d, e, f);}return 0;
}