2913584_ac_421ms_124k.cpp

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

#include <cmath>
#include <cstdio>
#include <fstream>
#include <iostream>
#include <algorithm>

using namespace std;

int nthd (__int64 n)
{
	if (n < 10) return 1;
	else return nthd (n / 10) + 1;
}

int digit (__int64 n, __int64 k)
{
	if (k == nthd (n)) return int (n % 10);
	else return digit (n / 10, k);
}

int consecutive (__int64 k)
{
	__int64 x = 1, n = 1;
	while (1 == 1)
	{
		while (x * 1000000 < k && nthd (n + 1000000) == nthd (n))
		{
			n += 1000000;
			k -= x * 1000000;
		}
		while (x * 10000 < k && nthd (n + 10000) == nthd (n))
		{
			n += 10000;
			k -= x * 10000;
		}
		while (x * 100 < k && nthd (n + 100) == nthd (n))
		{
			n += 100;
			k -= x * 100;
		}
		if (x >= k) break;
		k -= x;
		x = nthd(++n);
	}
	return digit(n, k);
}

int square (__int64 k)
{ 
	__int64 x = 1, n = 1;
	while (1 == 1)
	{
		while (x * 1000000 < k && nthd ((n + 1000000) * (n + 1000000)) == nthd (n * n))
		{
			n += 1000000;
			k -= x * 1000000;
		}
		while (x * 10000 < k && nthd ((n + 10000)*(n + 10000)) == nthd (n * n))
		{
			n += 10000;
			k -= x * 10000;
		}
		while (x * 100 < k && nthd ((n + 100) * (n + 100)) == nthd (n * n))
		{
			n += 100;
			k -= x * 100;
		}
		if (x >= k) break;
		k -= x;
		n++;
		x = nthd (n * n);
	}
	return digit(n * n, k);
}

int carry (__int64 k)
{
	while (1 == 1)
	{
		int x = consecutive (k) + square (k);
		if(x >= 10) return 1;
		if(x < 9) return 0;
		k++;
	}
}

int main ()
{
	while(1)
	{
		__int64 k;
		scanf ("%I64d", &k);

		if(k==0)
			break;
		
		cout << (consecutive (k) + square (k) + carry (k + 1)) % 10 << endl;
	}

	return 0;
}