TopCoder SRM 851 : Div1 Hard Based

聞いてしまうと簡単なのだが。
https://community.topcoder.com/stat?c=problem_statement&pm=18147

問題

f(n)は、nをb進数表記したとき桁和が2以下となる最小のbとする。
整数がN個指定されるので、それぞれのf(n)の和を求めよ。

解法

b進数表記が5桁以上となるのは、b^4≦max(n)となるとき。
nの上限は10^18程度なので、b進数表記が5桁以上となるケースは事前に列挙してしまおう。

残るケースはb進数表記で"1","10","11","20","100","101","110","200","1000","1001","1010","1100","2000"と限られるので、nごとにこれらを総当たりすればよい。

const ll mo=1000000007;
const ll ma=1LL<<60;

ll mult(ll a, ll b) {
	if(a==0||b==0) return 0;
	if(b==1) return a;
	if(ma/a<=b) return ma;
	return a*b;
}

ll mypow(ll a, ll n) {
	ll r=1;
	if(n<0) return 0;
	while(n) r=mult(r,((n%2)?a:1)),a=mult(a,a),n>>=1;
	return r;
}
map<ll,ll> memo;

class Based {
	public:
	ll hoge(ll v,int a,int b) {
		ll L=1,R=sqrt(v)+3;
		while(L+1<R) {
			ll M=(L+R)/2;
			if(mypow(M,a)+mypow(M,b)>=v) R=M;
			else L=M;
		}
		if(mypow(R,a)+mypow(R,b)==v) {
			return R;
		}
		else {
			return ma;
		}
		
	}
	
	ll hoge(ll v) {
		if(v<=6) return 2;
		ll ret=v-1;
		if(v%2==0) ret=v/2;
		if(memo.count(v)) ret=min(ret,memo[v]);
		
		ret=min(ret,hoge(v,3,3));
		ret=min(ret,hoge(v,3,2));
		ret=min(ret,hoge(v,3,1));
		ret=min(ret,hoge(v,3,0));
		ret=min(ret,hoge(v,3,-1));
		ret=min(ret,hoge(v,2,2));
		ret=min(ret,hoge(v,2,1));
		ret=min(ret,hoge(v,2,0));
		ret=min(ret,hoge(v,2,-1));
		
		return ret;
	}
	int solve(long long A, long long S, int N) {
		int i;
		for(ll a=2;a<=1000000;a++) {
			ll b=a*a*a*a;
			if(b>=ma) break;
			while(b<ma) {
				if(memo.count(b)==0) memo[b]=a;
				ll c=b;
				while(1) {
					if(memo.count(b+c)==0) memo[b+c]=a;
					if(c==0) break;
					c/=a;
				}
				b=mult(b,a);
			}
		}
		ll ret=0;
		FOR(i,N) (ret+=hoge(A+S*i))%=mo;
		return ret;
	}
}

まとめ

なぜこれを思いつけなかったか…。