UVa 256 Quirksome Squares：枚举||二次同余

UVa 256 Quirksome Squares：枚举||二次同余2014-07-28

256 - Quirksome Squares

Time limit: 3.000 seconds

http://uva.onlinejudge.org/index.php？option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=192

The number 3025 has a remarkable quirk: if you split its decimal representation in two strings of equal length （30 and 25） and square the sum of the numbers so obtained, you obtain the original number:

The problem is to determine all numbers with this property having a given even number of digits.

For example, 4-digit numbers run from 0000 to 9999. Note that leading zeroes should be taken into account. This means that 0001 which is equal to

is a quirksome number of 4 digits. The number of digits may be 2,4,6 or 8. Although maxint is only 32767 and numbers of eight digits are asked for, a well-versed programmer can keep his numbers in the range of the integers. However efficiency should be given a thought.

Input

The input of your program is a textflle containing numbers of digits （taken from 2,4,6,8）, each number on a line of its own.

Output

The output is a textfile consisting of lines containing the quirksome numbers （ordered according to the input numbers and for each input number in increasing order）.

Warning: Please note that the number of digits in the output is equal to the number in the corresponding input line : leading zeroes may not be suppressed.

Sample Input

Sample Output

000181000181

直接从0~9999枚举即可，因为等式右边一定是个完全平方数。

枚举法：

/*0.015s*/#include<bits/stdc++.h>using namespace std;const int maxn = 5;const int digit[maxn] = {0, 10, 100, 1000, 10000};vector<int> Store[maxn];int i, ii, j, X;void init（）{for （i = 0; i < 10000; ++i）{ii = i * i;for （j = 1; j < 5; ++j）{if （i < digit[j]）{X = ii / digit[j] + ii % digit[j];if （X == i） Store[j].push_back（ii）;}}}}int main（）{init（）;int N, M;while （~scanf（"%d", &N））{M = N >> 1;for （i = 0; i < Store[M].size（）; ++i）printf（"%0*d
", N, Store[M][i]）;}return 0;}