hdu 4394 Digital Square（bfs）

Digital Square

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

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

Sample Output

None

Source

2012 Multi-University Training Contest 10

Recommend

zhuyuanchen520 | We have carefully selected several similar problems for you: 4390 4398 4397 4396 4395

搜索题，首先证明出N位后缀只与M的后N位有关。比如三位数100a+10b+c平方后展开为 10000a^2+2000ab+100b^2+200ac+20bc+c^2很显然，平方后的最后一位只与c有关最后两位只与bc有关，最后三位abc都有关。

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

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

附上代码：

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cmath>
 5 #include <queue>
 6 using namespace std;
 7 __int64 n;
 8 struct node
 9 {
10     __int64 a;
11     int x;
12     friend bool operator < (node n1,node n2)  //优先队列，必须输出最小的数
13     {
14         return n1.a>n2.a;
15     }
16 } s1,s2;
17 
18 void BFS()
19 {
20     priority_queue <node> q;
21     while(!q.empty())
22         q.pop();
23     __int64 t;
24     s1.a=0;
25     s1.x=0;
26     q.push(s1);
27     while(!q.empty())
28     {
29         s1=q.top();
30         q.pop();
31         t=(__int64)pow(10.0,s1.x);  //从低位向高位搜
32         if(s1.a*s1.a%t==n)      //找到了就直接输出
33         {
34             printf("%I64d
",s1.a);
35             return;
36         }
37         for(int i=0; i<10; i++)
38         {
39             s2.x=s1.x+1;     //每次都向前进一位
40             s2.a=s1.a+i*t;   
41             if(s2.a*s2.a%(t*10)==n%(t*10))  //一位一位的匹配，匹配成功后，则放入队列
42                 q.push(s2);
43         }
44     }
45     printf("None
");
46 }
47 int main()
48 {
49     int T,m,i,j;
50     scanf("%d",&T);
51     while(T--)
52     {
53         scanf("%d",&n);
54         if(n%10==2||n%10==3||n%10==7||n%10==8)  //根据乘法的规律，任何一个数平方后的个位数不可能是这些数
55         {
56             printf("None
");
57             continue;
58         }
59         BFS();
60     }
61     return 0;
62 }