SGU107——987654321 problem

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

Input

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

Output

Write answer to the output.

Sample Input

8

Sample Output

0

简单数学，题目说，一个数字n、找n*n结果末尾是987654321的数。

先傻瓜式搜索，发现8位以下没有符合要求的；9位有4个，10位以上根据数学排列知识就搞定了。

最近在搞SGU，先从简单题目入手，碰到什么算法就搞什么算法。

#include<iostream>

#include<string.h>

#include<stdio.h>

#include<ctype.h>

#include<algorithm>

#include<stack>

#include<queue>

#include<set>

#include<math.h>

#include<vector>

#include<map>

#include<deque>

#include<list>

using namespace std;

int main()

{

//    for(int i=0;i<99999999;i++)

//    if(i*i==987654321)

//    printf("%d\n",i);

//    for(long long i=sqrt(987654321.0);i<=999999999;++i)

//        if( i*i%1000000000 == 987654321 )

//            printf("%d\n",i);

//}

//    111111111

//    119357639

//    380642361

//    388888889

//    611111111

//    619357639

//    880642361

//    888888889

    int n;

    while (scanf("%d",&n)!=EOF)

    {

        if (n<=8)

            printf("0\n");

        else if (n==9)

            printf("8\n");

        else

        {

            printf("72");

            for (int i=0;i<n-10;++i)

                printf("0");

                printf("\n");

        }

    }

}