本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2022-04-23 10:36:33

题解思路：

我们看看他有什么性质：

若我们去掉一个数的质因子，那么他就会向下走一格。

还有一个，我们看一下样例：$12$ 到 $2$ 那么我们先去掉一个质因子 $3$，再去掉一个质因子 $2$，或先取掉质因子 $2$，再去掉一个质因子 $3$，那么他们的路径权值是一样的。证明：

假设 $u$ 能走向 $v$，并 $u > v$，因为若从 $u$ 走向 $v$，那么把他质因子分解，既然 $u$ 能走向 $v$，那么 $v$ 一定是 $u$ 的某个因子的因子。所以 $v$ 一定是 $u$ 的因子，因为 $u$ 是在不断去掉质因子才达到 $v$ 的。

我们先把 $u$ 质因子分解：$u = p_1^{a_1} p_2^{a_2} p_3^{a_3} ...\ p_m^{a_m}$，那么你走下去，那么你会去掉一些质因子，就是 $a_1-x_1,a_2-x_2 ...\ a_m-x_m$，有的可能是去掉了零个，那么他的因子数为 $(a_1+1)(a_2+1)...(a_m+1)$，所以 $u$ 的因子数为 $(a_1+1)(a_2+1)...(a_m+1)$，而 $v$ 的因子数为 $(a_1-x_1+1)(a_1-x_2+1)...(a_m-x_m+1)$，那么我们把 $u$ 设为 $x$，那么假设我们先去掉 $p_i$ 的一个因子，就相当去掉一个 $\frac{\mathrm{x}}{\mathrm{a_i}}$，下一个我们去掉一个 $p_k$ 就相当于去掉： $\frac{\mathrm{xa_i}}{\mathrm{(a_i+1)(a_j + 1)}}+\frac{\mathrm{x}}{\mathrm{a_i+1}}$，想乘得 $\frac{\mathrm{a_i+a_j+1}}{\mathrm{(a_i+1)(a_j+1)}}x$，那么 $a_i$ 和 $a_j$ 交换了位置，那么其实不变，在推广到普通情况，也是相同的，证毕。

那么我们从 $x$ 走到 $y$，假设 $x>y$，那么 $x$ 每次去掉质因子，直到 $1$ 那么我们到一个点，比如 $y$ 这个点，那么他这个的最短路就是 $x$ 去因子的这条路，不然的话，你就没有这个更短。

然后若 $y$ 不是 $x$ 的因子，那么我们要选 $\gcd(x,y)$，这样才是最短路。若不选最大公因数的话，那么就会取掉多余的质因子，就不优了。

那么我们怎么算呢，因为他的质因子为 $p_1^{a_1} p_2^{a_2} p_3^{a_3} ...\ p_m^{a_m}$，走到他们的 $\gcd$ 就是：$p_1^{a'_1} p_2^{a'_2} p_3^{a'_3} ...\ p_m^{a'_m}$ 这就是他的过程，那么我们要把某个因子，要去掉一些因子，那么我们可以把他们换一下顺序，这个东西就是多次向系数。

那么我们求一下他们的全排列，但有重复的情况，比如全是相同的数，所以他的全排列有很多种，但都是一样的。

AC CODE:

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>
#include <map>
using namespace std;
typedef long long ll;
const int mod = 998244353;
ll D , fac[60] , inv[60];
vector <pair <ll , int>> p;
map <ll , vector<int>>mp;\/\/就相当于质因数分解的系数
vector <int> now;
ll gcd (ll a , ll b) {return b == 0 ? a : gcd (b , a % b);}\/\/求最大公因数
ll power (ll a , ll b) {\/\/快速幂，用来求逆元。
	ll res = 1;
	while (b) {
		if (b & 1) res = res * a % mod;
		a = a * a % mod;
		b >>= 1;
	}
	return res;
}
void dfs (int dep , ll sum) {\/\/暴力构造O(sqrt(n))
	if (dep == p.size()) {
		mp[sum] = now;\/\/取出来，放到一个map里
		return;
	}
	auto x = p[dep];
	now.push_back (0);
	dfs (dep + 1 , sum);
	now.pop_back();
	for (int i = 1; i <= x.second; ++ i) {
		sum *= x.first;
		now.push_back (i);
		dfs (dep + 1 , sum);
		now.pop_back ();
	}
}
void init () {\/\/预处理函数
	fac[0] = fac[1] = 1;
	for (int i = 2; i <= 59; ++ i)
		fac[i] = fac[i - 1] * i % mod;\/\/预处理阶乘
	for (int i = 1; i <= 59; ++ i)
		inv[i] = power (fac[i] , mod - 2);\/\/逆元因为mod是质数，所以可以预处理
	ll d = D;
	for (ll i = 2; i <= d \/ i; ++ i) {\/\/分解质因数.
		if (d % i == 0) {
			int cnt = 0;
			while (d % i == 0) {
				d \/= i;
				++ cnt;
			}
			p.push_back ({i , cnt});
		}
	}
	if (d > 1) p.push_back ({d , 1});
	dfs (0 , 1);\/\/构造
}
int main() {
	cin >> D;
	init();\/\/预处理
	int q;
	cin >> q;
	while (q --){
		ll u , v;
		cin >> u >> v;
		ll x = gcd (u , v);
		vector <int> a , b , c;\/\/把每个数的系数取出来
		a = mp[u] , b = mp[v] , c = mp[x];
		for (int i = 0; i < a.size(); ++ i) {\/\/做差，得出来的数就是答案的系数
			a[i] -= c[i];
			b[i] -= c[i];
		}
		ll sum = 0 , sum2 = 0 , ans = 1 , ans2 = 1;
		for (auto x : a) {\/\/计算
			if (!x) continue;
			sum += x;
			ans = ans * inv[x] % mod;
		}
		ans = ans * fac[sum] % mod;
		for (auto x : b) {\/\/计算
			if (!x) continue;
			sum2 += x;
			ans2 = ans2 * inv[x] % mod;
		}
		ans2 = ans2 * fac[sum2] % mod;
		ans = ans * ans2 % mod;\/\/最后相乘。
		cout << ans << endl;
	}
	return 0;
}