SGU[107] 987654321 problem

Description

描述

For given number N you must output amount of N-digit numbers, such, that last digits of their square is equal to 987654321.

对于任意给定的数N，你需要输出平方的末尾为987654321的N位数的个数。

Input

输入

Input contains integer number N (1<=N<=10⁶)

输入文件包含整数N（1 <= N <= 10⁶）。

Output

输出

Write answer in output file.

将答案输出在输出文件上。

Sample Input

样例输入

Sample Output

样例输出

Analysis

分析

在一定意义上，这也是一道数学题。

由于一个数平方的后X位，只与这个数字的后X位有关系，所以我们不妨使用下面的程序打一个表来看一下。

#include <iostream>

using namespace std;

int main()
{
	// sqrt(987654321) > 30000
	for(long long i = 30000; i <= 999999999; i++)
	{
		long long x = i * i;
		if(x % 1000000000 == 987654321)
		{ cout << i << " "; }
	}
	return 0;
}

打完表以后，我们发现只有8个数字满足条件，而且分布在100,000,000到999,999,999之间。

下面我们来推导满足题目条件的答案与输入的位数N的关系：

N <= 8，　　0
N == 9，　　8
N >= 10，这种情况我们要稍微考虑一下，由于平方后的后9位只与原数的后9位有关，因此就变成了给定后9位（第二种情况下的8个答案作为后九位数字），前面N-9位数字的方案数，由排列组合以及N位数的要求，不难的出结论，72 * 10^(N - 10)

有了这个结论，我们就可以在O(1)时间内得到答案。

Solution

解决方案

#include <iostream>

using namespace std;

int main()
{
	int N;
	cin >> N;
	if(N <= 8)
	{ cout << 0 << endl; }
	else if(N == 9)
	{ cout << 8 << endl; }
	else
	{
		cout << 72 << endl;
		while(N - 10)
		{
			cout << 0;
			N--;
		}
	}
	return 0;
}

这道题目最主要的是通过打表找出规律，然后通过数学方法，巧妙地将题目所要求的答案转换为前面N-9位上数字的排列方式，这样问题就得到了简化，也就很容易解决了。