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<=106)
输入文件包含整数N(1 <= N <= 106)。
Output
输出
Write answer in output file.
将答案输出在输出文件上。
Sample Input
样例输入
8
Sample Output
样例输出
0
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位上数字的排列方式,这样问题就得到了简化,也就很容易解决了。