AtCoder ABC #322 : G - Two Kinds of Base

凡ミスが最後まで取れず…。
https://atcoder.jp/contests/abc322/tasks/abc322_g

問題

整数N,Xが与えられる。
各桁が10未満の整数で、a進数表記とb進数表記の差がXとなるようなa,b≦Nとなる整数とa,bの対は何通りか。

解法

桁数をkとする。
k=2の時、最上位桁をi、最下位桁をjとすると、X/i==a-bかつb≧jかつa≦Nであればよい。
これはi,jを総当たりすれば容易に計算できる。

kが3以上の場合、最上位桁をiとすると

• Xは(a-b)で割り切れる
• i*a^(k-1)-i*b^(k-1)≦X

となる(a,b)の対を総当たりしよう。
(a,b)を定めると整数表記は一意に決まる。

ll N,X;
const ll mo=998244353;

ll dp[21][301010];

int check(int a,int b,int k) {
	ll v=X;
	for(int i=k-1;i>=1;i--) {
		ll x=dp[i][a]-dp[i][b];
		ll w=min({9LL,v/x,b-1LL});
		if(i==k-1&&w==0) return 0;
		v-=x*w;
	}
	if(v==0) return min(10,b);
	return 0;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>X;
	ll ret=0;
	
	for(i=1;i<=300000;i++) {
		dp[0][i]=1;
		FOR(j,19) dp[j+1][i]=dp[j][i]*i;
	}
	
	// k=2;
	for(i=1;i<=9;i++) FOR(j,10) if(X%i==0) {
		ll d=X/i;
		int mi=max(i+1,j+1)+d;
		if(mi<=N) (ret+=N-mi+1)%=mo;
	}
	
	ll num=0;
	for(k=3;k<=20;k++) {
		for(ll a=2;a<=N;a++) {
			if(dp[k-1][a]-dp[k-1][a-1]>X) break;
			for(ll b=a-1;b>=2;b--) {
				if(dp[k-1][a]-dp[k-1][b]>X) break;
				if(X%(a-b)==0) ret+=check(a,b,k);
			}
		}
	}
	
	cout<<ret%mo<<endl;
}

まとめ

凡ミスがもったいない。