CF1334E Divisor Paths（数论）

题意

给定一个数 $D$D，由 $D$D 生成以下图：

1. 每个点都为 $D$D 的因子
2. $x$x 和 $y$y 连有无向边边当且仅当 $x\mid y$x∣y 且 $\frac{y}{x}$xy​ 为素数
3. $(x,y)$(x,y) 的边权值为能整除 $x$x 但不能整除 $y$y 的数的个数

有 $q$q 个询问，每个询问给出 $u,v$u,v，求 $u$u 到 $v$v 的最短路径数。
$q\le 300000,D\le 10^{15}$q≤300000,D≤1015， $u,v$u,v 为 $D$D 的因子

分析

先来看看一条边的边权值，其实就是 $d\left(x\right)-d\left(y\right)$d(x)−d(y)。（ $d\left(x\right)$d(x) 为 $x$x 的约数个数）
那么考虑 $a$a 到其某个因子 $b$b 的一条路径，最优走法肯定是每次走向 $a$a 的一个因子。假设路径为 $a->x->y->b$a−>x−>y−>b。那么路径长为 $(d_a-d_x)+(d_x-d_y)+(d_y-d_b)=d_a-d_b$(da​−dx​)+(dx​−dy​)+(dy​−db​)=da​−db​。因此，从 $a$a 到 $b$b 的最短路径长为 $d_a-d_b$da​−db​
那么考虑 $u$u 到 $v$v， $u$u 先走到 $t$t， $t$t 再走到 $v$v。路径长即为 $d_u+d_v-2\ast d_t$du​+dv​−2∗dt​。不难看出 $t$t 为 $\gcd (u,v)$gcd(u,v) 时，路径长最小。
那么最短路径数就是 $way(u,t)\ast way(t,v)$way(u,t)∗way(t,v)。 $way(x,y)$way(x,y) 为 $x$x 到 $y$y 的路径数。
考虑 $way(x,y)$way(x,y) 的求法。
我们将 $x,y$x,y 表示成：
$x=\prod p_i^{k_i},y=\prod p_i^{t_i}$x=∏piki​​,y=∏piti​​，由于走一条路径相当于每次去掉一个质因子。于是第 $i$i 个质数 $p_i$pi​ 要走 $k_i-t_i$ki​−ti​ 步，记为 $c_i$ci​。
那么这个问题就变成了一个多重集排列问题，方案数为 $\frac{(\sum c_i)!}{\prod \left(c_i\right)!}$∏(ci​)!(∑ci​)!​
分解质因数采用 $pollard-rho$pollard−rho 算法。
总复杂度为 $O(D^{\frac{1}{4}}+qlogD)$O(D41​+qlogD)

代码如下

#include <bits/stdc++.h>
#include<ext/pb_ds/hash_policy.hpp>
#include<ext/pb_ds/assoc_container.hpp>
#define eps 1e-6
#define rg register
#define N 100005
using namespace __gnu_pbds;
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
typedef long double LD;
const int mod = 998244353;
struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }
    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};
gp_hash_table<LL, int, custom_hash> g;
LL z = 1;
LL read(){
	LL x, f = 1;
	char ch;
	while(ch = getchar(), ch < '0' || ch > '9') if(ch == '-') f = -1;
	x = ch - '0';
	while(ch = getchar(), ch >= '0' && ch <= '9') x = x * 10 + ch - 48;
	return x * f;
}
inline LL mul(LL a, LL b, LL p){
	return (a * b - LL(LD(a) / p * b) * p + p) % p;
}
LL ksm(LL a, LL b, LL p){
	LL s = 1;
	while(b){
		if(b & 1) s = mul(s, a, p);
		a = mul(a, a, p);
		b >>= 1;
	}
	return s;
}
LL f(LL x, LL c, LL n){
	return (mul(x, x, n) + c) % n;
}
int mr(LL a, LL x){
	if(ksm(a, x - 1, x) != 1) return 0;
	LL y = x - 1, t;
	while(!(y & 1)){
		y >>= 1;
		t = ksm(a, y, x);
		if(t == x - 1) return 1;
		if(t != 1 && t != x - 1) return 0;
	}
	return 1;
}
inline int isprime(LL x){
	if(x == 2 || x == 3 || x == 5 || x == 7 || x == 43) return 1;
	if(!mr(2, x) || !mr(3, x) || !mr(5, x) || !mr(7, x) || !mr(43, x)) return 0;
	return 1;
}
inline LL Max(LL a, LL b){
	return a > b? a: b;
}
LL PR(LL x){
	LL s = 0, t = 0, c = rand() % (x - 1) + 1, d;
	LL val = 1;
	for(rg int goal = 1; ; goal <<= 1, s = t){
		for(rg int step = 1; step <= goal; step++){
			t = f(t, c, x);
			val = mul(val, abs(t - s), x);
			if(step % 127 == 0){
				d = __gcd(val, x);
				if(d > 1) return d; 
			}
		}
		LL d = __gcd(val, x);
		if(d > 1) return d;
	}
}
void fac(LL x){
	if(x < 2) return;
	if(isprime(x)){
		g[x]++;
		return;
	}
	LL p = x;
	while(p >= x) p = PR(x);
	fac(x / p), fac(p);
}
LL a[N], b[N], d[N], v[N], cnt, ret;
LL inv[N], Fac[N], maxn = N - 5;
LL way(LL u, LL v){
	LL s = 0, ans = 1, p, i, j;
	u /= v; 
	for(auto t: g){
		p = t.first; i = 0;
		while(u % p == 0) u /= p, i++, s++;
		ans = ans * inv[i] % mod;
	}
	ans = z * ans * Fac[s] % mod;
	return ans;
}
int main(){
	srand(time(0));
	LL i, k, x, q, u, v, d, s, ans = 1;
	for(Fac[0] = i = 1; i <= maxn; i++) Fac[i] = Fac[i - 1] * i % mod;
	inv[maxn] = ksm(Fac[maxn], mod - 2, mod);
	for(i = maxn - 1; i >= 0; i--) inv[i] = inv[i + 1] * (i + 1) % mod;
	x = read(); q = read();
	fac(x);
	while(q--){
		u = read(); v = read();
		d = __gcd(u, v);
		ans = way(u, d) * way(v, d) % mod;
		printf("%d\n", ans);
	}
	return 0;
}