CF1334E题解

· · 题解

题解思路：

我们看看他有什么性质：

若我们去掉一个数的质因子，那么他就会向下走一格。

还有一个，我们看一下样例：12 到 2 那么我们先去掉一个质因子 3，再去掉一个质因子 2，或先取掉质因子 2，再去掉一个质因子 3，那么他们的路径权值是一样的。证明：

假设 u 能走向 v，并 u > v，因为若从 u 走向 v，那么把他质因子分解，既然 u 能走向 v，那么 v 一定是 u 的某个因子的因子。所以 v 一定是 u 的因子，因为 u 是在不断去掉质因子才达到 v 的。

我们先把 u 质因子分解：u = p_1^{a_1} p_2^{a_2} p_3^{a_3} ...\ p_m^{a_m}，那么你走下去，那么你会去掉一些质因子，就是 a_1-x_1,a_2-x_2 ...\ a_m-x_m，有的可能是去掉了零个，那么他的因子数为 (a_1+1)(a_2+1)...(a_m+1)，所以 u 的因子数为 (a_1+1)(a_2+1)...(a_m+1)，而 v 的因子数为 (a_1-x_1+1)(a_1-x_2+1)...(a_m-x_m+1)，那么我们把 u 设为 x，那么假设我们先去掉 p_i 的一个因子，就相当去掉一个 \frac{\mathrm{x}}{\mathrm{a_i}}，下一个我们去掉一个 p_k 就相当于去掉： \frac{\mathrm{xa_i}}{\mathrm{(a_i+1)(a_j + 1)}}+\frac{\mathrm{x}}{\mathrm{a_i+1}}，想乘得 \frac{\mathrm{a_i+a_j+1}}{\mathrm{(a_i+1)(a_j+1)}}x，那么 a_i 和 a_j 交换了位置，那么其实不变，在推广到普通情况，也是相同的，证毕。

那么我们从 x 走到 y，假设 x>y，那么 x 每次去掉质因子，直到 1 那么我们到一个点，比如 y 这个点，那么他这个的最短路就是 x 去因子的这条路，不然的话，你就没有这个更短。

然后若 y 不是 x 的因子，那么我们要选 \gcd(x,y)，这样才是最短路。若不选最大公因数的话，那么就会取掉多余的质因子，就不优了。

那么我们怎么算呢，因为他的质因子为 p_1^{a_1} p_2^{a_2} p_3^{a_3} ...\ p_m^{a_m}，走到他们的 \gcd 就是：p_1^{a'_1} p_2^{a'_2} p_3^{a'_3} ...\ p_m^{a'_m} 这就是他的过程，那么我们要把某个因子，要去掉一些因子，那么我们可以把他们换一下顺序，这个东西就是多次向系数。

那么我们求一下他们的全排列，但有重复的情况，比如全是相同的数，所以他的全排列有很多种，但都是一样的。

AC CODE:

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>
#include <map>
using namespace std;
typedef long long ll;
const int mod = 998244353;
ll D , fac[60] , inv[60];
vector <pair <ll , int>> p;
map <ll , vector<int>>mp;//就相当于质因数分解的系数
vector <int> now;
ll gcd (ll a , ll b) {return b == 0 ? a : gcd (b , a % b);}//求最大公因数
ll power (ll a , ll b) {//快速幂，用来求逆元。
    ll res = 1;
    while (b) {
        if (b & 1) res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}
void dfs (int dep , ll sum) {//暴力构造O(sqrt(n))
    if (dep == p.size()) {
        mp[sum] = now;//取出来，放到一个map里
        return;
    }
    auto x = p[dep];
    now.push_back (0);
    dfs (dep + 1 , sum);
    now.pop_back();
    for (int i = 1; i <= x.second; ++ i) {
        sum *= x.first;
        now.push_back (i);
        dfs (dep + 1 , sum);
        now.pop_back ();
    }
}
void init () {//预处理函数
    fac[0] = fac[1] = 1;
    for (int i = 2; i <= 59; ++ i)
        fac[i] = fac[i - 1] * i % mod;//预处理阶乘
    for (int i = 1; i <= 59; ++ i)
        inv[i] = power (fac[i] , mod - 2);//逆元因为mod是质数，所以可以预处理
    ll d = D;
    for (ll i = 2; i <= d / i; ++ i) {//分解质因数.
        if (d % i == 0) {
            int cnt = 0;
            while (d % i == 0) {
                d /= i;
                ++ cnt;
            }
            p.push_back ({i , cnt});
        }
    }
    if (d > 1) p.push_back ({d , 1});
    dfs (0 , 1);//构造
}
int main() {
    cin >> D;
    init();//预处理
    int q;
    cin >> q;
    while (q --){
        ll u , v;
        cin >> u >> v;
        ll x = gcd (u , v);
        vector <int> a , b , c;//把每个数的系数取出来
        a = mp[u] , b = mp[v] , c = mp[x];
        for (int i = 0; i < a.size(); ++ i) {//做差，得出来的数就是答案的系数
            a[i] -= c[i];
            b[i] -= c[i];
        }
        ll sum = 0 , sum2 = 0 , ans = 1 , ans2 = 1;
        for (auto x : a) {//计算
            if (!x) continue;
            sum += x;
            ans = ans * inv[x] % mod;
        }
        ans = ans * fac[sum] % mod;
        for (auto x : b) {//计算
            if (!x) continue;
            sum2 += x;
            ans2 = ans2 * inv[x] % mod;
        }
        ans2 = ans2 * fac[sum2] % mod;
        ans = ans * ans2 % mod;//最后相乘。
        cout << ans << endl;
    }
    return 0;
}