Solution #
First let’s factor , so . According to the definition, to factors are connected iff they differ by only one prime factor. And the weight of the edge is where is the number of factors of . So the length of a path where is
There are only two types of paths between and , one is and the other is . The length of the path of the first type is
The length of the second type is
Intuition tells us first type is always the shortest path.
All we need now is to calculate the number of shortest paths. Let . The number of shortest path between and is
Similarly we can calculate the number of paths between and .
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;
}