AtCoder ABC #161 : F - Division or Substraction

これも意外にシンプル。
https://atcoder.jp/contests/abc161/tasks/abc161_f

問題

正整数Nが与えられる。2以上N以下の整数Kのうち、以下を満たすものは何通りか。

• NがK未満になるまで以下を繰り返す。
  • NがKで割り切れるとき、NをKで割る。
  • NがKで割り切れないとき、NからKを引く。
• 最後N=1になる。

解法

後者の処理をやってもNはKで割れないので、前者の処理は先に行うことになる。
とすると、非負整数a,bを用いてと表現できれば条件を満たす。

• まずb=0の場合を列挙する。この場合、N-1=aK、すなわち(N-1)の約数のうち2以上のものがKとなりうる。
• 次にb≧1の場合を考える。この時点でKはNの約数でないといけないので候補が絞られる。
  • あとはそのKに対しbを増やしつつ、(N/K^b-1)がKで割れるか判定すればよい。

ll N;
set<ll> ret;

void hoge(ll N,ll a) {
	N/=a;
	while(N) {
		if((N-1)%a==0) {
			ret.insert(a);
			break;
		}
		if(N%a) return;
		N/=a;
	}
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	
	for(ll a=1;a*a<=N-1;a++) if((N-1)%a==0) {
		ret.insert(a);
		ret.insert((N-1)/a);
	}
	
	for(ll a=1;a*a<=N;a++) if(N%a==0) {
		hoge(N,a);
		hoge(N,N/a);
	}
	
	ret.erase(1);
	cout<<ret.size()<<endl;
	
	
}

まとめ

これ500ptでもいいんじゃないかと思ったら、Eより解いた人数多かったみたいね。