33. CF-Divisor Paths

链接

求从 \(x\) 到 \(y\) 的最短路径的数量。

显然应该从 \(x\) 走到 \(\gcd(x, y)\) 再走到 \(y\)，容易证明这样走是最优的。那么现在只需要把两段的最短路径数量分别求出来就行了。

最短路径数量随便排列组合算一下就好了。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int maxn = 1e5 + 5;
const ll mod = 998244353;
ll qpow(ll b, ll k) {
    ll ret = 1;
    while (k) {
        if (k & 1) ret = ret * b % mod;
        b = b * b % mod;
        k /= 2;
    }
    return ret;
}
vector<ll> prime;
ll fact[maxn], ifact[maxn];

void init_fact(int n) {
    fact[0] = 1;
    for (int i = 1; i <= n; ++i)
        fact[i] = fact[i - 1] * i % mod;
    ifact[n] = qpow(fact[n], mod - 2);
    for (int i = n - 1; i >= 0; --i)
        ifact[i] = ifact[i + 1] * (i + 1) % mod;
}

void solve() {
    ll x, y;
    cin >> x >> y;
    ll ans = 1;
    ll g = __gcd(x, y);
    x /= g, y /= g;
    vector<int> vx, vy;
    for (auto p : prime) {
        int cntx = 0, cnty = 0;
        while (x % p == 0) {
            x /= p;
            cntx++;
        }
        while (y % p == 0) {
            y /= p;
            cnty++;
        }
        vx.push_back(cntx);
        vy.push_back(cnty);
    }
    ans = ans * fact[accumulate(vx.begin(), vx.end(), 0)] % mod;
    ans = ans * fact[accumulate(vy.begin(), vy.end(), 0)] % mod;
    for (auto i : vx) ans = ans * ifact[i] % mod;
    for (auto i : vy) ans = ans * ifact[i] % mod;
    cout << ans << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    ll n;
    cin >> n;
    ll x = n;
    for (ll i = 2; i * i <= x; ++i) {
        if (x % i != 0) continue;
        prime.push_back(i);
        while (x % i == 0) x /= i;
    }
    if (x != 1) prime.push_back(x);
    init_fact(2333);
    int q;
    cin >> q;
    while (q--) {
        solve();
    }
}