AtCoder ARC #060 : D - 桁和 / Digit Sum

上位に海外勢が多いことを考えると悪くない順位？
http://arc060.contest.atcoder.jp/tasks/arc060_b

問題

f(b,N)はNをb進数表現したときの各桁の和とする。
整数N,Sが与えられる。
f(b,N)の10進数表記がSとなるbが存在するなら、最小値を示せ。

解法

まず以下のコーナーケースを処理する。

• N＜Sの時解無し
• N＝Sの時b=N+1

以下N＞Sのケースだけを考える。この場合b≦Nとなるのは明らかである。
自分はO(√N)で解いた。
まずb進数表記で３桁以上、すなわちb^2≦Nとなるbを総当たりし、実際にf(b,N)を求めた。

あとはb進数表記で2桁の場合を考える。
b進数表記で2桁であれば以下を満たさなければならない。

• b*P + Q = N (P,Q＜b)
• P+Q = S

Pを1～√Nまで総当たりし、条件を満たすP,Qが存在するかチェックした。

ll N,S;

ll f(ll b,ll n) {
	if(n<b) return n;
	return f(b,n/b)+(n%b);
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>S;
	if(S>N) return _P("-1\n");
	if(N==S) return _P("%lld\n",N+1);
	set<ll> SS;
	for(ll b=2;b*b<=N;b++) if(f(b,N)==S) SS.insert(b);
	
	for(ll p=1;p*p<N && p<=S;p++) {
		ll m=S-p;
		if(N-m>=0 && (N-m)%p==0) {
			ll b=(N-m)/p;
			if(b>p && b>m) SS.insert((N-m)/p);
		}
		
	}
	
	if(SS.size()) return _P("%lld\n",*SS.begin());
	return _P("-1\n");
}

まとめ

なんとかしてO(√N)で解こうとしたらこうなった。