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

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

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

题目链接: https://oj.xjtuicpc.com/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;
}