PKU 1019 Number Sequence

問題

11212312341234512345612345671234567812345678912345678910123456789101112345678910...
と続く数列がある。

この数列のi番目の数字を求めよ。

制約条件

i≦2147483647

方針

i桁までの数の列を書き終えたときの列の長さをlen[i]とする。
（1121231213412345123456...123456789の長さがlen[0]）
これは、len[i - 1]と、等差数列の和の公式から計算できる。

するとlen[i]との比較によって、何桁の数字までが列に含まれるかがわかる。
次にその列において何番目の数であるかを求める。
これは等差数列の和の公式を二分探索すればいい。

今、112123...nという列のk番目の数字を求めたいことになっているので、
k番目の数字が何桁の数であるかを求める。
それで、その桁の何番目の数字に含まれているかを求めて、
その数字のその番目の数字を求めてやればいい。

ソースコード

const int SZ = 7;
ll len[SZ], n[SZ], len2[SZ], pw[30];
int a[SZ];

void solve(ll k){
	int keta = 0;
	while(k >= len[keta]) k -= len[keta++];
	
	ll lo = 0, hi = n[keta], mid;
	while(lo + 1 < hi){
		mid = (lo + hi) / 2;
		if(mid * a[keta] + (keta + 1) * mid * (mid + 1) / 2 <= k) lo = mid;
		else hi = mid;
	}
	k -= lo * a[keta] + (keta + 1) * lo * (lo + 1) / 2;
	
	int keta2 = 0;
	while(k >= len2[keta2]) k -= len2[keta2++];
	
	char digit[30];
	sprintf(digit, "%lld\n", pw[keta2] + k / (keta2 + 1));
	
	k %= keta2 + 1;
	printf("%c\n", digit[k]);
}

int main()
{
	rep(i, SZ){
		a[i] = i ? a[i - 1] + n[i - 1] * i : 0;
		n[i] = i ? n[i - 1] * 10 : 9;
		len[i] = a[i] * n[i] + (i + 1) * n[i] * (n[i] + 1) / 2;
		
		len2[i] = (i + 1) * n[i];
	}
	pw[0] = 1;
	rep(i, 29) pw[i + 1] = pw[i] * 10;
	
	int cs;
	cin >> cs;
	while(cs--){
		ll k;
		cin >> k;
		solve(k - 1);
	}
	return 0;
}