SGU 107 987654321 problem (数论)

time limit per test: 0.5 sec. 

memory limit per test: 4096 KB

http://acm.sgu.ru/problem.php?contest=0&problem=107

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<=106)

Output

Write answer to the output.

Sample Input

8
      

Sample Output

思路：

先暴力求出9位数中平方末尾为987654321的数有几个--8个。

又由于高位平方不影响低位结果，所以就有了代码中的结论。

(PS：那8个数是111111111,119357639,380642361,388888889,611111111,619357639,880642361,888888889)

完整代码：

/*15ms,835KB*/

#include<cstdio>

int main(void)
{
    int n;
    scanf("%d",&n);
    if(n<9)
        putchar('0');
    else if(n==9)
        putchar('8');
    else
    {
        putchar('7');
        putchar('2');
        n-=10;
        while(n--)
            putchar('0');
    }
    return 0;
}