题解 | #补天裂#

偏乱搞的做法。

注意到转进制后极大部分是 2 位的，剩下的我们直接跑暴力即可。

考虑枚举令转 $kk$ 进制后为 $abab$，即 $n=ak+bn=ak+b$，然后你枚举 $aa$，打个表，然后就能摸出来 $bb$ 的范围是个区间了。

然后再钦定下 $a,ba,b$ 哪个比较大计算一下贡献即可。

#include <bits/stdc++.h>
#define int long long
#define pb push_back
using namespace std;
int n,st[40],cnt=0,m;

int solve(int k) {
	if(k<=0) return 0;
	int x=n,tot=0;
	while(x) st[tot++]=x%k,x/=k;
	int mx=0;
	for(int i=0;i<tot;i++) mx=max(mx,st[i]);
	++mx; int p=1,res=0;
	for(int i=0;i<tot;i++) res=res+p*st[i],p*=mx;
	return res;
}

int cal(int x) {
	if(x<=0) return 0;
	return x*(x+1)/2;
}

int Floor(int x,int y) {
	if(x%y) return x/y;
	return x/y-1;
}

void sol() {
	cin>>n; int ans=0; cnt=0; int m=n;
	for(int i=1;i<=10000;i++) {
//		cout<<": "<<i<<'\n';
		int fir=n-i*m;
//		if(!fir) break ;
		int t=Floor((m-fir),(i+1));
//		ans+=2;
//		cout<<fir<<" "<<t<<'\n';
		if(t<=0||m<2||m-t<2) {
			break ;
		}
//		for(int j=m;j>=m-t;j--) ans+=solve(j);
//		if(1<=i&&i>=t) {
//			ans+=
//		}
//		for(int j=0;j<=t;j++) {
//			int qwq=max(i,fir+j*i)+1;
//			ans+=qwq*i+fir+j*i;
//		}
		int l=0,r=t,res=min(t,(i-fir)/i);
//		while(l<=r) {
//			int mid=(l+r)>>1;
//			if(i>=fir+mid*i) res=mid,l=mid+1;
//			else r=mid-1;
//		}
		if(res!=-1) {
			ans+=(res+1)*i*(i+1)+(res+1)*fir+i*cal(res); 
		}
//		for(int j=res+1;j<=t;j++) {
//			ans+=fir*i+i*i*j+i*j+fir;
//			int qwq=max(i,fir+j*i)+1;
//			ans+=(fir+j*i+1)*i+fir+j*i;
//		}
		ans+=(t-res)*fir*(i+1)+(t-res)*i+i*i*(cal(t)-cal(res))+i*(cal(t)-cal(res));
		m=m-t-1;
	}
//	cout<<m<<'\n';
	for(int j=m;j>=2;j--) ans+=solve(j);
	cout<<ans<<'\n';
}

signed main() {
	cin.tie(0); ios::sync_with_stdio(false);
	int T; cin>>T; while(T--) sol();
	return 0;
}