yukicoder : No.3187 Mingle

これはすんなり。
https://yukicoder.me/problems/no/3187

問題

正整数Nが与えられる。
今変数aの初期値がNとする。
aが2以下になるまで以下を繰り返すとき、必要な操作回数の期待値を求めよ。

• 1以上a以下の正整数bをランダムに選ぶ。その後、aからa % bを引く。

解法

f(n) :=a=nの状態から、aが2以下に至るまでの操作回数の期待値
とする。nを列挙するのではなく、bを列挙することを考える。
bを選んだあと、a=kbに遷移するのは、a=(kb+1)～(kb+(b-1))である。

よってf(n)を小さい順に埋めることを考える。
f(n)がわかっているとき、nの約数dを列挙し、f(n+1)～f(n+d-1)に値を計上していこう。

ll N;
ll mo;

ll dp[603030];
vector<int> D[606060];

ll modpow(ll a, ll n = mo-2) {
	ll r=1;a%=mo;
	while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1;
	return r;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>mo;
	for(i=1;i<=N;i++) {
		for(j=i;j<=N;j+=i) D[j].push_back(i);
	}
	
	for(i=3;i<=N;i++) {
		(dp[i+1]+=dp[i])%=mo;
		dp[i]=(i*modpow(i-D[i].size())%mo+dp[i]%mo*modpow(i-D[i].size()))%mo;
		FORR(d,D[i]) if(d>1) {
			(dp[i+1]+=dp[i])%=mo;
			(dp[i+d]+=mo-dp[i])%=mo;
		}
	}
	cout<<dp[N]<<endl;
	
}

まとめ

aではなくbを列挙することに至ればすぐ。