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