F 数论

题意

给出 $a，b$，要求：

$\frac{c}{d}-\frac{e}{f}=\frac{a}{b}$ 且 $d,f\lt b$

试求：$c，d，e，f$

思路

原式变形可得到 $\frac{cf-be}{df}=\frac{a}{b}$，将 $\frac{a}{b}$ 化为最简分数 $\frac{a^{‘}}{b^{‘}}$，由最简分数的唯一性可得：

$b^{‘}=df$，$a{‘}=cf-de$

当 $b^{‘} \neq b$ 时，我们令 $d=1,f=b^{‘},c=1$，可以得到：$e=a{‘}+b{‘}$，这是一组可行解。

当 $b{‘} = b$ 时，我们不能直接令$f=b^{‘}$。我们希望能找到 $b$ 的互质因子 $d,f$，使得 $b = df$，从而代入上述方程，通过扩展欧几里得解出 $c$ 和 $e$。如果找不到互质因子，那就无解。

如何找到对应的互质因子呢？我们可以使用线性筛找出整数 $b$所含的某个质数因子 $pfactor(b)$，对于每个整数 $b$，进行如下操作，就可以得到最小互质因子 $d, f$:

ll k = pfactor[b], d = 1, f = b;
while (k != 1 && f % k == 0) {
    d *= k;
    f /= k;
}

当然，上面的代码有可能会得到 $d = b, f = 1$，这代表找不到互质因子，此时无解。

然后我们就可以求不定方程 $a{‘}=cf-de$，得到最后答案。

时间复杂度 $O(n+t\log(n))$

代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int N = 2e6 + 5;
bool isnp[N];
int pfactor[N];
vector<int> primes;

void init() {
    isnp[0] = isnp[1] = 1;
    pfactor[1] = 1;
    for (int i = 2; i < N; ++i) {
        if (!isnp[i]) {
            primes.emplace_back(i);
            pfactor[i] = i;
        }
        for (int x : primes) {
            if (1LL * x * i >= N) break;
            isnp[x * i] = 1;
            pfactor[x * i] = x;
            if (i % x == 0) break;
        }
    }
}

ll ex_gcd(ll a, ll b, ll &x, ll &y) {
    if (b == 0) {
        x = 1, y = 0;
        return a;
    }
    ll gcd = ex_gcd(b, a % b, y, x);
    y -= (a / b) * x;
    return gcd;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int t;
    init();
    cin >> t;
    while(t--) {
        ll a, b;
        cin >> a >> b;

        ll gcd = __gcd(a, b);

        if (gcd > 1) {
            ll c = (a + b) / gcd, d = b / gcd, e = 1, f = 1;
            cout << c << ' ' << d << ' ' << e << ' ' << f << '\n';
            continue;
        }

        ll k = pfactor[b], d = 1, f = b;
        while (k != 1 && f % k == 0) {
            d *= k;
            f /= k;
        }

        if (f == 1) {
            cout << "-1 -1 -1 -1\n";
            continue;
        }

        ll c, e;
        ex_gcd(d, f, e, c);
        e = -e;
        while (c <= 0 || e <= 0) {
            c += d;
            e += f;
        }
        c *= a, e *= a;

        cout << c << ' ' << d << ' ' << e << ' ' << f << '\n';
    }
    return 0;
}