Codeforces ECR #191 : F. Shortest GCD Paths

なるほど。
https://codeforces.com/contest/2233/problem/F

問題

正整数N,A,Bが与えられる。
1～NのN点からなる完全グラフを考える。
２点間(u,v)の間の距離d(u,v)は、max(u.v)/GCD(u,v)とする。２点a,bの最短距離を求めよ。

解法

d(ag,bg)=d(a,b)なので、A,Bは互いに素であると考えてよい。
遷移すべき値は、Aの約数とBの約数の倍数だけである。
dp(a,b) := 現在値がa*(B/b)となる状態に至る最短距離
とする。

dp(A,B)=0から始めて、dp(1,1)を求めたい。
dp(a,b)で遷移先の値はA,Bの約数だけなので、遷移の数は余り多くなく、TLEせず間に合う。

ll N,A,B;

vector<ll> D1,D2;
ll TD1[2020][2020];
ll TD2[2020][2020];
vector<int> C1[2020],C2[2020];
ll memo[2020][2020];

ll dfs(int x,int y) {
	if(x==0&&y==0) return 0;
	if(memo[x][y]>=0) return memo[x][y];
	ll ret=1LL<<60;
	FORR(d1,C1[x]) FORR(d2,C2[y]) if(d1+d2) ret=min(ret,max(D1[d1],D2[d2])+dfs(TD1[x][d1],TD2[y][d2]));
	return memo[x][y]=ret;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>A>>B;
	ll g=__gcd(A,B);
	A/=g;
	B/=g;
	
	D1.clear();
	D2.clear();
	for(i=1;i*i<=A;i++) if(A%i==0) {
		D1.push_back(i);
		if(i*i!=A) D1.push_back(A/i);
	}
	for(i=1;i*i<=B;i++) if(B%i==0) {
		D2.push_back(i);
		if(i*i!=B) D2.push_back(B/i);
	}
	sort(ALL(D1));
	sort(ALL(D2));
	int L1=D1.size();
	int L2=D2.size();
	FOR(i,L1) {
		x=0;
		C1[i].clear();
		for(j=i;j>=0;j--) {
			if(D1[i]%D1[j]==0) C1[i].push_back(j);
			while(x<i&D1[i]>D1[x]*D1[j]) x++;
			if(D1[i]%D1[j]==0&&D1[x]*D1[j]==D1[i]) TD1[i][j]=x;
		}
		reverse(ALL(C1[i]));
	}
	FOR(i,L2) {
		x=0;
		C2[i].clear();
		for(j=i;j>=0;j--) {
			if(D2[i]%D2[j]==0) C2[i].push_back(j);
			while(x<i&D2[i]>D2[x]*D2[j]) x++;
			if(D2[i]%D2[j]==0&&D2[x]*D2[j]==D2[i]) TD2[i][j]=x;
		}
		reverse(ALL(C2[i]));
	}
	MINUS(memo);
	cout<<dfs(L1-1,L2-1)<<endl;
		
}

まとめ

意外と素直な解法だった。