Description
给定一个数 (D le 10^{15}),对于所有 (D) 的因数作为结点,构造无向图,如果两个点 (x>y) 满足 (x/y) 是一个质数,那么我们就在 (x,y) 之间连一条边,边权等于 (x) 有而 (y) 没有的因子的个数。给定 (q le 3 imes 10^5) 个询问,每次给定两个点 (u,v),要求回答这张图上 (u,v) 的最短路径的条数。
Solution
图上两个点 (x,y) 如果满足 (x | y),那么 (x,y) 之间的距离就是 (d(y)-d(x)),其中 (d(x)) 表示 (x) 的因子个数,并且最短路的数量就是 (y/x) 的所有质因子构成的多重集合的排列数目(这非常类似于一个把质因子一个个塞进去的过程)。
因此 (p,q) 间的最短路一定会经过 ((p,q)),并且可以拆成 (p o (p,q) o q) 两段,最短路长度相加,最短路数量相乘。
于是所求即为 (P(p/(p,q)) imes P(q/(p,q))),瓶颈在于 (P) 的计算即质因子分解。
考虑到这里出现的所有质因子都是 (D) 的质因子,而 (D) 的质因子显然不会超过 (O(log D)) 种,因此暴力枚举即可。
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 998244353;
const int N = 1000005;
int D,q,fac[N],ifac[N];
int qpow(int p,int q)
{
return (q&1?p:1) * (q?qpow(p*p%mod,q/2):1) % mod;
}
int inv(int p)
{
return qpow(p,mod-2);
}
vector <int> facs;
void Prefac(int x)
{
int lim=sqrt(x+0.5), t=x;
for(int i=1;i<=lim;i++)
{
if(t && t%i==0)
{
facs.push_back(i);
t/=i;
while(t && i>1 && t%i==0) t/=i;
}
}
if(facs.size() && facs.back()!=t && t) facs.push_back(t);
}
vector <pair<int,int>> Factor(int x)
{
vector <pair<int,int>> ans;
for(int i:facs)
{
if(i==1) continue;
int cnt=0;
while(x && x%i==0)
{
++cnt;
x/=i;
}
if(cnt)
{
ans.push_back({i,cnt});
}
}
// for(auto i:ans) cout<<i.first<<","<<i.second<<" ";
// cout<<endl;
return ans;
}
int Perm(vector <pair<int,int>> vec)
{
int ans = 1;
int sum = 0;
for(auto pr:vec)
{
int num=pr.first, cnt=pr.second;
sum += cnt;
}
// cout<<"add "<<sum<<endl;
ans = fac[sum];
for(auto pr:vec)
{
int num=pr.first, cnt=pr.second;
ans *= ifac[cnt];
// cout<<"del "<<num<<" "<<cnt<<endl;
ans %= mod;
}
return ans;
}
int Calc(int x)
{
vector <pair<int,int>> vecfac = Factor(x);
int ans = Perm(vecfac);
return ans;
}
signed main()
{
ios::sync_with_stdio(false);
cin>>D;
cin>>q;
Prefac(D);
// for(int i:facs) cout<<i<<",";
// cout<<endl;
fac[0]=ifac[0]=1;
for(int i=1;i<N;i++)
{
fac[i]=fac[i-1]*i%mod;
ifac[i]=inv(fac[i]);
}
for(int i=1;i<=q;i++)
{
int x,y;
cin>>x>>y;
int g=__gcd(x,y);
int ans1=Calc(x/g);
int ans2=Calc(y/g);
cout<<ans1*ans2%mod<<endl;
}
}
/*
874918473783561
1
1 874918473783561
*/