2015
05-24

# Digital Square

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….)

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.

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.

3
3
21
25

None
11
5

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

#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
const __int64 INF = 100000000000LL;

struct Node
{
__int64 m, x;
Node()
{
m = 0;
x = 0;
}
};

__int64 ten[10];

void init()
{
__int64 num = 1;
for(int i=0;i<10;++i)
{
ten[i] = num;
num *= 10;
}
}

int getLength(__int64 x)
{
if(x == 0) return 1;
int len = 0;
while(x > 0)
{
x /= 10;
++ len;
}
return len;
}

int main()
{
int caseNumber;
__int64 n;
init();
scanf("%d", &caseNumber);
while(caseNumber--)
{
scanf("%I64d", &n);
int len = getLength(n);
queue<Node> q;
q.push(Node());
while(!q.empty())
{
Node u = q.front();
if(u.x == len) break;
for(int i=0;i<10;++i)
{
Node v;
v.m = u.m + ten[u.x] * i;
v.x = u.x + 1;
if((v.m * v.m) % ten[v.x] == n % ten[v.x]) q.push(v);
}
q.pop();
}
__int64 ans = INF;
while(!q.empty())
{
Node node = q.front();
if(ans > node.m)
ans = node.m;
q.pop();
}
if(ans == INF) printf("None\n");
else           printf("%I64d\n", ans);
}
return 0;
}