Codeforces ECR #085 : E. Divisor Paths

よくもまぁいろいろ問題設定思いつくよね。
https://codeforces.com/contest/1334/problem/E

問題

正整数Dが与えられる。
この整数Dに対し、以下のグラフを考える。

• Dの各約数vに対し、頂点を作る。
• 2つの約数x,yのうち、x/yが素数になる場合、両者に対応する点の間に無向辺を張る。その際、辺の長さはxの約数であってyの約数でないものの数とする。

以下のクエリに答えよ。

• Dの約数2つu,vが与えられる。u-vの最短経路を成すパスは何通りか。

解法

経路を考えてみると、一旦uからGCD(u,v)に遷移し、その後vに移動する。
その際、遷移の過程ではuに対し素数の除算を繰り返し、その後GCD(u,v)から素数の乗算を繰り返してvに遷移する。
余分な除算・乗算さえしなければ、除算内での素数の順番や乗算内での素数の順番は経路長に影響しない。

そこで、u/GCD(u,v)を素因数分解したときの素数の並べ方と、v/GCD(u,v)を素因数分解したときの素数の並べ方の積を計算しよう。

ll D;
int Q;
vector<ll> P;

const ll mo=998244353;
ll comb(ll N_, ll C_) {
	const int NUM_=400001;
	static ll fact[NUM_+1],factr[NUM_+1],inv[NUM_+1];
	if (fact[0]==0) {
		inv[1]=fact[0]=factr[0]=1;
		for (int i=2;i<=NUM_;++i) inv[i] = inv[mo % i] * (mo - mo / i) % mo;
		for (int i=1;i<=NUM_;++i) fact[i]=fact[i-1]*i%mo, factr[i]=factr[i-1]*inv[i]%mo;
	}
	if(C_<0 || C_>N_) return 0;
	return factr[C_]*fact[N_]%mo*factr[N_-C_]%mo;
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>D>>Q;
	
	ll v=D;
	for(ll a=2;a*a<=v;a++) {
		if(v%a==0) {
			P.push_back(a);
			while(v%a==0) v/=a;
		}
	}
	if(v>1) P.push_back(v);
	
	while(Q--) {
		ll U,V;
		cin>>U>>V;
		
		vector<int> A,B,C;
		int sum[2]={};
		FOR(i,P.size()) {
			x=0;
			while(U%P[i]==0) x++,U/=P[i];
			while(V%P[i]==0) x--,V/=P[i];
			A.push_back(max(x,0));
			B.push_back(max(-x,0));
			sum[0]+=A.back();
			sum[1]+=B.back();
		}
		ll ret=1;
		FORR(c,A) {
			ret=ret*comb(sum[0],c)%mo;
			sum[0]-=c;
		}
		FORR(c,B) {
			ret=ret*comb(sum[1],c)%mo;
			sum[1]-=c;
		}
		cout<<ret<<endl;
		
		
		
	}
	
	
}

まとめ

こういう数値1個からグラフを作る問題、いろいろ作問に応用ができそう。