题目来源: Educational Codeforces Round 85: E. Divisor Paths

题目链接: https://codeforces.com/contest/1334/problem/E

题目来源: XJTUOJ-1167 zxh的高考幸运法阵

题目链接: https://oj.skyair.org/problem/1167

题面

给定一个正整数 \(D\), 根据如下规则构造一个图 \(\mathfrak D\):

  1. \(\mathfrak D\) 的每一个节点都是 \(D\) 的一个正因数.
  2. \(\mathfrak D\) 的两个节点 \(x,y\) 如果满足: \(x>y\), \(y\mid x\)\(x/y\) 是素数, 那么 \(\mathfrak D\) 上就会有一个 \(x,y\) 之间的无向边, 边权为 \(d(x)-d(y)\). 其中 \(d\) 是除数函数, 表示因子个数.

现在有 \(q\) 次询问, 每次询问 \(\mathfrak D\) 中两个节点 \(u,v\) 之间的最短路的个数 \(N(u,v)\), 输出对 \(p\) 取模后的结果.

备注

在 Codeforces 中的题目 \(p=998244353\).

在 XJTUOJ 中的题目 \(p=919260817\). 注意, \(919260817\) 是一个质数.

数据范围

\[ 1\le D\le 10^{15} \]

\[ 1\le q\le3\cdot10^5 \]

\[ 1\le u,v\le D \]

题解

\(S(x)\)\(x\) 的因子构成的集合.

考虑在 \(\mathfrak D\) 边上行走的效果: 设 \(u,v\) 之间连接了一条边, \(u>v\): 从 \(v\)\(u\) 是 “向上走”, 编号乘上了一个素数, \(S\) 增加了一些因子, 边权就是 \(S\) 增加的因子数; 从 \(u\)\(v\) 是 “向下走”, 编号除以了一个素数, \(S\) 减少了一些因子, 边权就是 \(S\) 减少的因子数.

考虑整除的情形: 即 \(x\) 走到 \(y\) 的过程, 其中 \(x\mid y\). 这样至少要增加 \(d(y)-d(x)\) 个因子. 这时, 最理想的情况就是只增加因子, 不减少因子, 这样的路径长度就是 \(d(y)-d(x)\). 不断地向上走, 不断地乘上一个素数, 直到节点到达 \(y\), 这样的路径就是一条最短路. 设 \(y/x=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_s^{\alpha_s}\), 则一条最短路需要乘 \(\alpha_1\)\(p_1\), 乘 \(\alpha_2\)\(p_2\), \(\cdots\), 乘 \(\alpha_s\)\(p_s\). 乘素数的顺序不同, 所代表的最短路也不同. 依组合数学, 一共有 \[ \frac{\left(\displaystyle\sum_{i=1}^s\alpha_i\right)!}{\displaystyle\prod_{i=1}^s\alpha_i!}=\frac{(\alpha_1+\alpha_2+\cdots+\alpha_s)!}{\alpha_1!\alpha_2!\cdots\alpha_s!}=N(x,y)\tag1 \] 种排列方式, 这就是这种情形的答案.

对于不整除的情形, 我们需要分别乘一些素数和除以一些素数. 乘和除的顺序是怎样的? 应该是先尽可能地向下走, 再向上走. 即, 先从 \(x\) 走到 \(\gcd(x,y)\), 之后再从 \(\gcd(x,y)\) 走到 \(y\). 这是因为, 向下走会减少之后每一步向上走的时候增加的因子数目, 同时避免向上走导致的向下走删除的因子数目的增多. 这两步走法都是整除的情形, 可以用公式 \((1)\) 计算. 由乘法原理, 走法数就是这两步走法数的乘积, 即 \[ N(x,y)=N(\gcd(x,y),x)\cdot N(\gcd(x,y),y) \]

综上所述: \[ N(x,y)=\begin{cases} \displaystyle\frac{(\alpha_1+\alpha_2+\cdots+\alpha_s)!}{\alpha_1!\alpha_2!\cdots\alpha_s!}&x\mid y&\displaystyle \frac yx=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_s^{\alpha_s}\\ N(\gcd(x,y),x)\cdot N(\gcd(x,y),y)&x\nmid y \end{cases} \]

在算法实现上, 阶乘可以预处理, 算出 \(y/x\) 的标准分解式即可直接得到答案. 由于 \(x,y,y/x\) 都是 \(D\) 的因子, 标准分解式中的质数一定是 \(D\) 的质因子, 而 \(D\) 的质因子最多有 \(\log D\) 个, 于是可以预处理 \(D\) 的所有质因子, 然后计算标准分解式时, 计算每个质因子的指数即可. 分解复杂度为 \(O(\log D)\), 计算复杂度为 \(O(\log D)\). 总时间复杂度为 \(O(q\log D)\).

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
class llp; // 见我的模板
vector<ll> ps;
map<ll, int> cnt;
const int mx = 1e5;
llp pows[mx], invs[mx];
void dvd(ll d)
{
for (ll p = 2; p * p <= d; ++p)
if (d % p == 0)
{
ps.push_back(p);
do
d /= p;
while (d % p == 0);
}
if (d != 1)
ps.push_back(d);
}
ll gcd(ll a, ll b)
{
return b ? gcd(b, a % b) : a;
}
llp solve(ll u, ll v)
{
if (u == v)
return 1;
if (u > v)
swap(u, v);
if (v % u != 0)
return solve(gcd(u, v), u) * solve(gcd(u, v), v);
cnt.clear();
ll up = v / u;
ll tcnt = 0;
for (ll p : ps)
while (up % p == 0)
up /= p, ++cnt[p], ++tcnt;
llp ans = pows[tcnt];
for (auto x : cnt)
ans *= invs[x.second];
return ans;
}
int main()
{
pows[0] = 1;
for (int i = 1; i < mx; ++i)
pows[i] = pows[i - 1] * i;
invs[mx - 1] = ~pows[mx - 1];
for (int i = mx - 2; i >= 0; --i)
invs[i] = invs[i + 1] * (i + 1);
ll d;
scanf("%lld", &d);
dvd(d);
int q;
scanf("%d", &q);
for (int t = 0; t < q; ++t)
{
ll v, u;
scanf("%lld%lld", &u, &v);
printf("%d\n", (int)solve(v, u));
}
return 0;
}