凡ミスが最後まで取れず…。
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; }
まとめ
凡ミスがもったいない。