2913236_wa.cpp

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>

__int64 num[] = {9,100,1000,10000,100000,1000000,10000000,100000000,1000000000,10000000000};
__int64 st[] = {1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000,10000000000};
__int64 st2[100];
__int64 num2[100];

int get1(__int64 k)
{
	__int64 i, t, s;
	char str[20];

	for(i = 0; ; i++)
		if(k > num[i])
			k -= num[i];
		else
			break;
	i++;
	k--;
	t = k/i;
	s = k%i;
	t = st[i-1]+t;
	_i64toa(t,str,10);
	return str[s]-'0';
}

__int64 power(__int64 a,__int64 b)
{
	if(b==0)
		return (__int64)1;
	return a*power(a,b-1);
}

void init()
{
	__int64 i;
	__int64 t, tot;
	char a1[200], b1[200];

	st2[1] = 1;tot = num2[0] = 0;
	for(i = 1; tot < ((__int64)1<<33); i++)
	{
		t = (__int64)floor(sqrt(power(10,i)));
		if(t*t!=power(10,i))
			t++;
		_i64toa(t*t,a1,10);
		_i64toa((t-1)*(t-1),b1,10);
		if(strlen(a1)!=strlen(b1)+1)
			while(1);
		st2[i+1] = (__int64)t;
		num2[i] = (st2[i+1]-st2[i]);
		num2[i] *= i;
		tot += num2[i];
	}
}

int get2(__int64 k)
{
	__int64 i, t, s;
	char str[100];

	for(i = 1; ; i++)
		if(k > num2[i])
			k -= num2[i];
		else
			break;
	k--;
	t = k/i;
	s = k%i;
	t = st2[i]+t;
	k = t;
	_i64toa(k*k,str,10);
	return str[s]-'0';
}

int main()
{
	__int64 k;
	int t, s, sum;

	init();
	while(scanf("%I64d",&k)==1,k)
	{
		t = get1(k);
		s = get2(k);
		sum = s+t;
		while(1)
		{
			k++;
			t = get1(k);
			s = get2(k);
			if(t+s<9)
				break;
			else
				if(t+s>9)
				{
					sum++;
					break;
				}
		}
		printf("%d\n",sum%10);
	}
	return 0;
}