4859999_ac_0ms_280k.cpp

来自「部分PKU上的源码」· C++ 代码 · 共 76 行

#include<iostream>
using namespace std;
__int64 l[50];
int getl(int i)
{
	int geshu=9;
	for(int j=1;j<i;j++) geshu*=10;
	return l[i-1]+geshu*i;
}
__int64 getal(__int64 i)
{
	__int64 geshu=9;
	for(int j=1;j<i;j++) geshu*=10;
	__int64 t= (l[i-1]+i+l[i-1]+i*geshu)*geshu/2;
	return t;
}
int get3it(int i,int x)
{
	int num=0,k[20],j=0;;
	while(i){num++;k[j++]=i%10;i/=10;}
	return k[num-x];
}
int get2it(int x)
{
	int tll=0;
	int all=0;
	for(int j=1;;j++)
	{
		int num=0,temp=j;
		while(temp){num++;temp/=10;}
		tll=num;
		if(all+tll>=x)
		{
			return get3it(j,x-all);
		}
		else all+=tll;
	}
}
int getit(int i,int n)
{
	int tll=l[i-1];
	int all=0;
	for(int j=1;;j++)
	{
		tll+=i;
		if(all+tll>=n)
		{
			return get2it(n-all);
		}
		else all+=tll;
	}
}
int main()
{
	int i,testnumber,n;
	__int64 all;
	cin>>testnumber;
	l[0]=0;
	for(i=1;i<45;i++) l[i]=getl(i);
	for(int count=0;count<testnumber;count++)
	{
		cin>>n;
		all=0;
		for(i=1;;i++)
		{
			__int64 temp=getal(i);
			if(all+temp>=n)
			{
				cout<<getit(i,n-all)<<endl;
				break;
			}
			else all+=temp;
		}
	}
	return 0;
}