Editorial of Codeforces 1334E

Solution #

First let’s factor $D$ , so $D=p_1^{e_1}p_2^{e_2}\dots p_k^{e_k}$ . According to the definition, to factors are connected iff they differ by only one prime factor. And the weight of the edge is $d(x)-d(y)$ where $d(i)$ is the number of factors of $i$ . So the length of a path where $v_1<v_2<\dots<v_k$ is $d(v_k)-d(v_i)$

There are only two types of paths between $x$ and $y$ , one is $x \rightarrow\gcd(x,y)\rightarrow y$ and the other is $x \rightarrow \operatorname{lcm}(x,y) \rightarrow y$ . The length of the path of the first type is

$d(x)-d(\gcd(x,y))+d(y)+d(\gcd(x,y))=d(x)+d(y)-2\cdot d(\gcd(x,y))$

The length of the second type is

$d(\operatorname{lcm}(x,y))-d(x)+d(\operatorname{lcm}(x,y))-d(y)=2\cdot d(\operatorname{lcm}(x,y))-d(x)-d(y)$

Intuition tells us first type is always the shortest path.

All we need now is to calculate the number of shortest paths. Let $\frac x {\gcd(x,y)}=p_1^{e_1}p_2^{e_2}\dots p_k^{e_k}$ . The number of shortest path between $x$ and $\gcd(x,y)$ is

$\dfrac {(e_1+e_2+\dots e_k)!}{e_1!\cdot e_2!\cdot\ldots\cdot e_k!}$

Similarly we can calculate the number of paths between $y$ and $\gcd(x,y)$ .

Code #

#include <bits/stdc++.h>
 
#define forn(i, n) for (int i = 0; i < int(n); ++i)
#define for1(i, n) for (int i = 1; i <= int(n); ++i)
#define fore(i, l, r) for (int i = int(l); i <= int(r); ++i)
#define ford(i, n) for (int i = int(n)-1; i >= 0; --i)
#define pb push_back
#define eb emplace_back
#define ms(a, x) memset(a, x, sizeof(a))
#define F first
#define S second
#define endl '\n'
#define all(x) (x).begin(),(x).end()
 
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int INF = 0x3f3f3f3f;
mt19937 gen(chrono::high_resolution_clock::now().time_since_epoch().count());
template<typename... Args>
void write(Args... args) { ((cout << args << " "), ...); cout<<endl;}
 
constexpr ll mod=998244353;
ll binpow(ll a,int b){
    ll res=1;
    for(;b;b>>=1){
        if(b&1) res=res*a%mod;
        a=a*a%mod;
    }
    return res;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    ll n;
    cin>>n;
    vector<ll> factor;
    for(ll f=2;f*f<=n;f++){
        if(n%f==0){
            factor.push_back(f);
            while(n%f==0) n/=f;
        }
    }
    if(n>1) factor.push_back(n);
    array<ll,1000> fac,inv;
    fac[0]=inv[0]=1;
    for(int i=1;i<1000;i++) fac[i]=fac[i-1]*i%mod;
    inv[999]=binpow(fac[999],mod-2);
    for(int i=998;i>0;i--) inv[i]=inv[i+1]*(i+1)%mod;
 
    auto count=[&](ll x,ll y){
        x/=y;
        ll ret=1,sum=0;
        for(auto it:factor){
            int tmp=0;
            while(x%it==0){
                tmp++;
                x/=it;
            }
            ret=ret*inv[tmp]%mod;
            sum+=tmp;
        }
        ret=ret*fac[sum]%mod;
        return ret;
    };
    int q;
    cin>>q;
    while(q--){
        ll x,y;
        cin>>x>>y;
        ll g=gcd(x,y);
        cout<<count(x,g)*count(y,g)%mod<<endl;
    }
    return 0;
}

Editorial of Codeforces 1334E - Divisor Paths

Solution #

Code #