yukicoder : No.890 移調の限られた旋法

全体で15分切ってたので、時間通り出ておきたかった。
https://yukicoder.me/problems/no/890

問題

　
整数N,Kが与えられる。
円周上等間隔に並んだN個の点のうちK個を選んだ時、回転対称性がある、すなわち360度未満で回転させて元の形状と一致するものは何通りか。

解法

f(x) := 点x個分右に回転させたとき元と同じ形状になるようなKの選び方の組み合わせ
とする。N/xが整数の場合、N/x=Pとする。すなわち、長さxの同じ並びがP回繰り返した形状ということになるので、
f(x) = Comb(N/P, K/P)
となる。
ここで、この形状は長さがxの約数を繰り返した可能性もある。そこで
g(x) := 最少で点x個分右に回転させたとき元と同じ形状になるようなKの選び方の組み合わせ
とするとg(x) = f(x) - sum(g(y)) (yはx未満のyの約数)となる。
よってxの小さい順にg(x)を求め、またxの倍数zに対しf(z)からg(x)を順次引くことでg(x)を確定させていこう。

g(x)の総和が解。

int N,K;

ll mo=1000000007;
ll comb(ll N_, ll C_) {
	const int NUM_=1400001;
	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;
}
ll dp[1010101];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	
	for(i=1;i<N;i++) if(N%i==0) {
		int L=N/i;
		if(K%L==0) {
			dp[i]=comb(i,K/L);
		}
	}
	ll ret=0;
	for(i=1;i<N;i++) if(dp[i]) {
		ret+=dp[i];
		for(j=i*2;j<=N;j+=i) if(N%j==0) (dp[j]+=mo-dp[i])%=mo;
		
	}
	cout<<ret%mo<<endl;
}

まとめ

問題文を読んで6や8が問題に関係あるのかと思ってしまった。