今天又是硕果仅存的一题o(╯□╰)o

time limit per test: 0.5 sec.  memory limit per test: 4096 KB

 

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，问你存在多少个平方后最后9位为“987654321”的N位数。

思路：1<=N<=10⁶,显然直接暴力枚举是不可能的，可想到某个数的平方后的低位只与原数的低位有关（如：11^2=121,111^111=12321,211^2=4521），故只要找到符合条件平方后低位出现987654321的最低位数即可。可先写个方程找出符合条件的数，即可知道当位数为9存在8个低位为987654321的数。故当N<9时输出0，当N=9时输出8，当N=10时输出8*9=72，当N>10时，每增加1就多输出一个0（如：N=11，输出720）。

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 using namespace std; 6 /*#define inf 1000000000 7 int main() 8 { 9     int n=987654321,flag=0;10     for(long long i=10000000;i<=1000000000;i++)11     {12         long long t=i*inf+n,m=sqrt(t);//printf("%lld\n",t);13         if(m*m==t){printf("%lld %lld\n",m,t);flag=1;}14     }15     if(!flag)printf("qunima");16 }*/17 int main()18 {19     int n;20     cin>>n;21     long long res=9;22     if(n<9)cout<<'0';23     else if(n==9)cout<<'8';24     else25     {26         cout<<"72";27         for(int i=2; i<=n-9; i++)cout<<'0';28     }29     cout<