Digital Square
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 743 Accepted Submission(s): 139

Problem Description
Given an integer N,you should come up with the minimum nonnegative integer M.M meets the follow condition: M2%10x=N (x=0,1,2,3….)

Input
The first line has an integer T( T< = 1000), the number of test cases. For each case, each line contains one integer N(0<= N <=109), indicating the given number. Output For each case output the answer if it exists, otherwise print None. Sample Input 3 3 21 25 Sample Output None 11 5

?Download sourceCode.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <cmath>
 
using namespace std;
 
int n;
long long ans = 10000000000LL;
 
long long dfs(long long shi, long long now){
    if(shi > n)
        return 0;
    int sheng = n % shi;
    for(long long i = 0; i <= 9; i ++){
        long long a = i * shi + now;
        long long aa = a * a % (shi * 10);
        long long nn = n % (shi * 10);
        if(aa == nn){
            //printf("a=%I64d aa=%I64d shi=%I64d\n", a, aa, shi);
            if(aa == n){
                ans = min(ans, a);
            }
            else
                dfs(shi * 10, a);
        }
    }
    return 0;
}
 
int main(){
    int t;
    scanf("%d", &t);
    while(t --){
            ans = 10000000000LL;
        scanf("%d", &n);
        if(n == 0){
            printf("0\n");
            continue;
        }
        if(n == 1000000000){
            printf("None\n");
            continue;
        }
        dfs(1, 0);
        if(ans == 10000000000LL)
            printf("None\n");
        else
            printf("%I64d\n", ans);
    }
    return 0;
}