數論 - SGU 107 987654321 problem 987654321 problem Problem's Link

Mean: 

略

analyse:

這道題目是道簡單題.

不過的确要好好想一下：

通過簡單的搜尋可以知道，在N<9時答案一定為0，而N=9時有8個解。由于題目隻是問“最後9位”，是以N=10的時侯第10位的取值不會對平方和的“最後9位”産生影響，而第10位上有9種取值方法，是以N=10的時侯，答案是72.

同樣可以知道，當N>10的時侯，隻要在72後加入(N-10)個“0”即可.

Time complexity: O(n)

view code

/**

* -----------------------------------------------------------------

* Copyright (c) 2016 crazyacking.All rights reserved.

*       Author: crazyacking

*       Date  : 2016-01-06-18.55

*/

#include <queue>

#include <cstdio>

#include <set>

#include <string>

#include <stack>

#include <cmath>

#include <climits>

#include <map>

#include <cstdlib>

#include <iostream>

#include <vector>

#include <algorithm>

#include <cstring>

using namespace std;

typedef long long(LL);

typedef unsigned long long(ULL);

const double eps(1e-8);

* SGU 107. 987654321 problem

* n < 9: ans = 0.

* n = 9: ans = 8

* n > 9: ans = 8*9*(10^(n-10))

int main(int argc, char **argv)

{

   int n = 0;

   scanf("%d", &n);

   if(n < 9)

       printf("0");

   else if(n == 9)

       printf("8");

   else

   {

       printf("72");

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

           printf("0");

   }

   return 0;

}