Digital Square

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 649    Accepted Submission(s): 297

Problem Description

Given an integer N,you should come up with the minimum

 

nonnegative

 integer M.M meets the follow condition: M

²%10

^x=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 <=10

⁹), 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

 

 

Source

 

 

Recommend

zhuyuanchen520

 

 

 

题目：给出n，求出最小的m，满足m^2  % 10^k = n，其中k=0,1,2

 

只要有一个x满足条件便行了

我们可以初步发现，某个数个位确定，那么平方的最后一位肯定是确定的，那么如果后两们确定，那么平方的最后两们也是确定的，这可以通过乘法的规律得到

那我们只需要BFS一下，不断地找满足最后指定位数的数，1位，2位，……直到找到第一个满足条件的。

注意这里可能是100001这种情况

所以记录当前数字大小，当前位置，可能暂时的高位为0，以后下一个添加的数为多少

 

 

#include
      
       #include
       
        #include
        
         #include
         
          using namespace std;struct node{    long long num;    int len,start;    node(){}    node(long long _num,int _len,int _start):num(_num),len(_len),start(_start){}    bool operator < (const node a) const{        return a.num
          
            q;    while(!q.empty())        q.pop();    int len=0;    long long tmp=n;    while(tmp){        len++;        tmp/=10;    }    node cur,next;    q.push(node(0,0,0));    while(!q.empty()){        cur=q.top();        q.pop();        if(cur.len==len){       //已经和n的位数相同，说明已经找到             printf("%I64d\n",cur.num);            return ;        }        if(cur.start<=9)    //如果>9，说明已经遍历了0-9，不再加入队列              q.push(node(cur.num,cur.len,cur.start+1));        next=cur;        next.len++;     //长度加1         next.num=next.num+fac[next.len-1]*next.start;    //在最高位加上这个数        next.start=0;   //下一次又从0开始         if((next.num*next.num)%fac[next.len]==n%fac[next.len])            q.push(next);    }    printf("None\n");}int main(){    //freopen("input.txt","r",stdin);    fac[0]=1;    for(int i=1;i<18;i++)        fac[i]=fac[i-1]*10;    int t;    scanf("%d",&t);    while(t--){        scanf("%I64d",&n);        BFS();    }    return 0;}