yukicoder : No.2829 GCD Divination

これは割と自明かな…。
https://yukicoder.me/problems/no/2829

問題

正整数Nが与えられる。
以下をN=1となるまで行うとき、処理回数の期待値を求めよ。

• 1以上N以下の整数Mを等確率で選び、NをGCD(N,M)で更新する。

解法

Nが遷移する値は、元のNの約数のみである。
またGCD(N,M)が取りえる値も元のNの約数のみである。
よって約数包除の要領で、Nの遷移先とその遷移確率を愚直に求めて行きながら、メモ化再帰を行えばよい。

int N;
vector<int> V;

map<int,double> M;
double hoge(int v) {
	if(v==1) return 0;
	if(M.count(v)) return M[v];
	int x=lower_bound(ALL(V),v)-V.begin();
	int dp[500]={};
	int i,j,k;
	for(j=x;j>=0;j--) if(v%V[j]==0) {
		dp[j]=v/V[j];
		for(i=j+1;i<=x;i++) if(V[i]%V[j]==0) dp[j]-=dp[i];
	}
	double ret=0;
	FOR(i,x) if(dp[i]) ret+=dp[i]*hoge(V[i]);
	
	ret=ret/(v-1.0)+v/(v-1.0);
	
	return M[v]=ret;
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	for(i=1;i*i<=N;i++) if(N%i==0) {
		V.push_back(i);
		if(i*i!=N) V.push_back(N/i);
	}
	sort(ALL(V));
	
	_P("%.12lf\n",hoge(N));
		
	
}

まとめ

これ他で出ててもおかしくないな。