题解 CF1334E 【Divisor Paths】

· · 题解

我们发现，每次走过一条路径都是减少/增加一个质因子。而且边权是减少/增加一个质因子后减少/增加的因数个数。那么显然有：x\to y的最优路径一定是x\to gcd(x,y)\to y。因为这样能保证减少/增加的质因子是其他所有方案减少/增加的质因子的子集，那么显然减少/增加的因数个数是最少的。

又因为x\to gcd(x,y)的路径上，因数一定是不停减少，不会增加的。而无论删除质因子的顺序如何，减少的因数集合一定是固定不变的。所以删去质因子的顺序可以任意排列。gcd(x,y)\to y的路径同理。

那么算法就很显然了。我们先分解D，然后将\frac{x}{gcd(x,y)}质因数分解。（因为\frac{x}{gcd(x,y)}包含的质因子一定是D的质因子，所以我们可以直接利用先前分解好的D的质因子一个一个尝试即可）我们只需要知道\frac{x}{gcd(x,y)}质因数分解出的质因子个数cnt即可，这样一次分解利用之前的预处理数据后复杂度是\log D。证明显然。

那么x\to gcd(x,y)的方案数就是\frac{cnt!}{\prod _{\text{v is prime }}cnt_v!}。gcd(x,y)\to y的方案数同理。然后乘在一起就好了。

P.S. 有个小问题，就是为什么不走lcm(x,y)中转。这里我只会一个感性证明：显然这两种方法，经过的路径条数都是一样的。而走lcm的话，路径上所有数都会更大些，增减一个质因子导致的因子的增加减少也会更多些。（纯口胡，不知道对不对）。这个问题我也问过一些大佬，大家的解释大多是“感性证明”，“看起来走gcd就是对的”，“你觉得不保险可以都走一遍，大不了常数\times2”。如果哪位神仙会严格证明请留言教教我QAQ。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<vector>
#include<queue>
#define vi vector<int>
#define pb push_back
#define mk make_pair
#define pii pair<int,int>
#define rep(i,a,b) for(int i=(a),i##end=(b);i<=i##end;i++)
#define fi first
#define se second
typedef long long ll;
using namespace std;
const int maxn=3e5+100;
const int mod=998244353;
ll d,q;
ll prime[maxn],prime_cnt,frac[maxn];
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
int ksm(ll num,ll t) {
    ll res=1;num%=mod;
    for(;t;t>>=1,num=num*num%mod) {
        if(t&1)res=num*res%mod;
    }
    return res%mod;
}
ll solve(ll u) {
    ll a=1,b=1,tot=0;//分子分母
    rep(i,1,prime_cnt) {
        ll cnt=0;while(u%prime[i]==0)u/=prime[i],cnt++;
        b=b*frac[cnt]%mod;tot+=cnt;
    }
    a=frac[tot];
    return a*ksm(b,mod-2)%mod;
}
int main() {
    ios::sync_with_stdio(0);
    cin>>d>>q;
    frac[0]=frac[1]=1;//预处理阶乘
    rep(i,2,100)frac[i]=frac[i-1]*i%mod;
    ll tmp=d;
    for(ll i=2;i*i<=d;i++) {
        if(tmp%i==0)prime[++prime_cnt]=i;
        while(tmp%i==0)tmp/=i;
    }
    if(tmp>1)prime[++prime_cnt]=tmp;
    rep(i,1,q) {
        ll u,v;cin>>u>>v;ll g=gcd(u,v);
        cout<<solve(u/g)*solve(v/g)%mod<<endl;
    }
    return 0;
}