SRM 508 Div 1 Easy DivideAndShift

不参加の回の。この回のMediumはEditorial見たけどよくわからない……orz

問題概要

次のようなゲームをする。
1からNまでの番号のついたスロットがある。
スロットの中には物体が入っていて、1番のスロットの中のものを取り出すことができる。
スロットには次のような操作が出来る。操作を何度か行い、M番目に入っている物体を取り出すことがゲームの目的である。

  • 左シフト(n番にn+1番に入っていた物体を入れる。N番には1番に入っていた物体が入る)
  • 右シフト(n番にn-1番に入っていた物体を入れる。1番にはN番に入っていた物体が入る)
  • 分割。Nを割り切る素数pを選ぶ。スロットを1番からN/p番、N/p+1番からN/p*2番……とp個に分割する。目的の物体が入っているグループ以外を全て取り除く。N/pが新たなNとなる。


M番目のスロットに入っている物体を取り除くのに必要な操作の最小の回数を求めよ。

制約条件

N≦1000000

方針

分割の操作とシフトの操作は入れ替えて、操作の合計回数は変えずにシフトを最後にまとめて行うようにできる。


したがって、分割の仕方を決めれば、最小の操作の回数は一通りに決まる。
分割は、pを合成数でもよくして、「コストが素因数の個数」であると考えることができる。
つまりNの約数についてそれぞれ分割の仕方が一つ対応するので、約数を全部しらべればいい。

ソースコード

int nf(int n){
	int ret=0;
	for(int i=2;i*i<=n;i++)while(n%i==0)ret++, n/=i;
	if(n>1)ret++;
	return ret;
}

class DivideAndShift {
	public:
	int getLeast(int N, int M) 
	{
		M--;
		int ans=min(M,N-M);
		for(int i=2;i<=N;i++)if(N%i==0){
			int m=M%(N/i);
			ans=min(ans, nf(i) + min(N/i - m, m));
		}
		return ans;
	}
};