DISCO presents ディスカバリーチャンネル コードコンテスト2019 予選 : D - チップ・ストーリー ～黄金編～

Cまでは順調なのに最後がダメ。
https://beta.atcoder.jp/contests/ddcc2019-qual/tasks/ddcc2018_qual_d

問題

1以上10^12以下の整数Nを当てたい。
Nをk進数表記したとき、各桁の値の総和をA[k]とする。
A[2]～A[30]が与えられたとき、条件を満たすNを答えよ。

解法

k=10の例を考えると、N%(k-1) = A[k]%(k-1)であることがわかる。
あとは(k-1)=2,3,5,7,11,13,17,19,23,29のケースを求めれば、CRTでN%(2*3*5*7*11*13*19*23*29)がわかるので、Nの候補は絞られる。
後は条件を満たすか候補毎に試すだけ。

int A[31];

ll ext_gcd(ll p,ll q,ll& x, ll& y) { // get px+qy=gcd(p,q)
	if(q==0) return x=1,y=0,p;
	ll g=ext_gcd(q,p%q,y,x);
	y-=p/q*x;
	return g;
}

pair<ll,ll> crt(ll a1,ll mo1,ll a2,ll mo2) { // return (x,y) y=lcm(a1,a2),x%mo1=a1,x%mo2=a2
	ll g,x,y,z;
	g=ext_gcd(mo1,mo2,x,y);
	a1=(a1%mo1+mo1)%mo1;a2=(a2%mo2+mo2)%mo2;
	if(a1%g != a2%g) return pair<ll,ll>(-1,0); // N/A
	__int128_t lcm=mo1*(mo2/g);
	if(lcm<mo1) return pair<ll,ll>(-2,0); // overflow
	
	__int128_t v=a1+((a2-a1)%lcm+lcm)*x%lcm*(mo1/g);
	return make_pair(((v%lcm)+lcm) % lcm,lcm);
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	
	
	ll a=1;
	for(int i=2;i<=30;i++) cin>>A[i];
	
	vector<int> V={3,5,7,11,13,17,19,23,29};
	pair<ll,ll> p={A[3]%2,2};
	FORR(v,V) {
		p=crt(p.first,p.second,A[v+1]%v,v);
		if(p.first<0) return _P("invalid\n");
	}
	while(p.first<=1000000000000LL) {
		for(i=2;i<=30;i++) {
			ll c=p.first;
			ll t=0;
			while(c) t+=c%i, c/=i;
			if(A[i]!=t) break;
		}
		if(i==31) {
			cout<<p.first<<endl;
			return;
		}
		
		p.first+=p.second;
	}
	
	
	cout<<"invalid"<<endl;
}

まとめ

10進数と9の関係には気づいたが、そこからCRTに持って行けなかった。