これも意外にシンプル。
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より解いた人数多かったみたいね。