CF1334E Divisor Paths 题解

题目链接：CF1334E Divisor Paths

题意：

给出正整数 \(D\) 和一张图 \(G\) ，满足：

• \(G\) 中每个节点都与 \(D\) 的因子一一对应
• 存在无向边 \((x, y)\) 当且仅当 \(y\) 整除 \(x\) 且 \(\frac{x}{y}\) 是质数
• 边 \((x, y)\) 的长度为 \(d_x-d_y\) ，其中 \(d_k\) 代表正整数 \(k\) 的 因子个数

共 \(q\) 次询问，每次给出 \(D\) 的因子 \(u\) 和 \(v\)，求 \(G\) 中节点 \(u, v\) 之间的最短路条数

输入格式：

第一行包含一个正整数 \(D\) （ \(1 \le D \le 10^{15}\) ）— 构建图的数。

第二行包含一个正整数 \(q\) （ \(1 \le q \le 3 \times 10^5\) ）— 查询数量。

接下来的每行，每行包含两个整数 \(v\) 和 \(u\) （ \(1 \le v, u \le D\) ）。保证 \(D\) 能同时被 \(v\) 和 \(u\) 整除（ \(v\) 和 \(u\) 都是 \(D\) 的约数）。

输出格式：

输出 \(q\) 个整数 — 对于每个查询，输出两个给定顶点之间最短路径的数量，取模为 \(998244353\)。

图论+数论+计数，好像啥都有。

容易发现 \(x\) 到 \(y\) 的最短路一定是 \(x \leadsto \gcd(x,y)\leadsto y\) 。

因为这样能保证其增量（即增加/减少的质因子）是其他方案增量的子集。

考虑 \(x\leadsto \gcd(x,y)\) 的路径，此时 \(x\) 的因数个数一定在不断减少，且删除质因子的顺序不影响因数集合。

因此删除质因子的顺序可以任意排列。\(\gcd(x,y)\leadsto y\) 同理，只不过从减少变为增加了。

考虑分解 \(\frac{x}{\gcd(x,y)}\) ，记每种质因子的格式为 \(k_i\) ，且 \(k = \sum k_i\) ，则左侧的方案数为（右侧同理） \[ \frac{k!}{\prod_{i \in \mathbb{P}} k_i!} \] 时间复杂度 \(\mathcal{O}(q\log D)\)

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
const int mod = 998244353;
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(3e5 + 15))

int d,q,pcnt,p[N],fac[N];
int gcd(int a,int b) { return (b == 0) ? a : gcd(b, a % b); }
int qpow(int a,int b) { 
    int c = 1; a %= mod;
    for(; b; a = a * a % mod, b >>= 1)
        if(b & 1) c = a * c % mod;
    return c;
}
int solve(int u)
{
    int a = 1, b = 1, tot = 0;
    for(int i = 1; i <= pcnt; i++)
    {
        int k = 0; while(u % p[i] == 0) { u /= p[i], ++k; }
        b = b * fac[k] % mod; tot += k;
    }
    a = fac[tot]; return a * qpow(b, mod - 2) % mod;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> d >> q; fac[0] = fac[1] = 1;
    for(int i = 2; i <= 100; i++) fac[i] = fac[i - 1] * i % mod;
    int tmp = d;
    for(int i = 2; i * i <= d; i++)
    {
        if(tmp % i == 0) p[++pcnt] = i;
        while(tmp % i == 0) tmp /= i;
    }
    if(tmp > 1) p[++pcnt] = tmp;
    for(int i = 1, u,v; i <= q; i++)
    {
        cin >> u >> v; int g = gcd(u, v);
        cout << solve(u / g) * solve(v / g) % mod << '\n';
    }
    return 0;
}

---

参考文献：

[1] https://www.luogu.com.cn/blog/GavinZheng/solution-cf1334e