F 数论

题意

给出 ，要求：

且

试求：

思路

原式变形可得到 ，将 化为最简分数 ，由最简分数的唯一性可得：

，

当 时，我们令 ，可以得到：，这是一组可行解。

当 时，我们不能直接令。我们希望能找到 的互质因子 ，使得 ，从而代入上述方程，通过扩展欧几里得解出 和 。如果找不到互质因子，那就无解。

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

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

当然，上面的代码有可能会得到 ，这代表找不到互质因子，此时无解。

然后我们就可以求不定方程 ，得到最后答案。

时间复杂度

代码

#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;
}