hdu 4394(bfs)

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4394

思路：n的个位可以由m的个位确定，n的十位可以由m的个位和十位确定，以上同理，故直接bfs搜索就可以，先搜个位满足要求的，然后在满足要求的个位上扩展到十位上（其实就是就是在个位数前加个数，变成2位数）。

View Code

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<queue>
 5 #include<cmath>
 6 using namespace std;
 7 typedef long long ll;
 8 struct Node{
 9     ll num;
10     int len;//长度
11     bool operator < (const Node &p) const {
12         return p.num<num;
13     }
14 };
15 ll n,ans;
16 
17 bool bfs(){
18     priority_queue<Node>Q;
19     Node p,q;
20     p.num=0,p.len=0;
21     Q.push(p);
22     while(!Q.empty()){
23         p=Q.top();
24         Q.pop();
25         ll tmp=(ll)pow(10,p.len);
26         if(p.num*p.num%tmp==n){
27             ans=p.num;
28             return true;
29         }
30         //扩展
31         for(int i=0;i<10;i++){
32             q.len=p.len+1;
33             q.num=p.num+i*tmp;
34             if(q.num*q.num%(tmp*10)==n%(tmp*10))
35                 Q.push(q);
36         }
37     }
38     return false;
39 }
40 
41 
42 int main(){
43     int _case;
44     scanf("%d",&_case);
45     while(_case--){
46         scanf("%I64d",&n);
47         if(bfs()){
48             printf("%I64d\n",ans);
49         }else
50             puts("None");
51     }
52     return 0;
53 }