分支限界法有三种策略，分别是FIFO、LIFO和LC（least cost）。BFS属于分支限界法的一种，通常采用FIFO策略，采用LIFO策略的情况比较少见，因为多数情况下这两种策略效果几乎相同。分支限界法采用LC策略时，通常用BFS+优先队列来实现。

问题链接：。

题意简述：输入测试用例数量t，输入t个正整数n，求最小的m，满足m^2%10^x=n，其中k=0,1,2,...。

问题分析：x是不定的，用暴力法试探m是不现实的。有关模除％的问题，可以用从低位开始逐步试探的方法，即先试探个位，然后十位、百位、千位等等。已知n的情况下，m的低位是有限的。例如n=21，那么m的个位只能是１或９，其他的数字是无法满足给定条件的。解决本问题需要明确以下几点：

1.对于m，从最低位开始试探，m的每位的数字可以是０－９，这时匹配n的最低位；

2.试探完１位再试探２位、３位和４位等等，分别匹配n的最低１位、２位、３位和４位等等；

3.m起始值：0,1,2,3,......；

4.显式剪枝条件：低位不匹配；

5.LC函数（优先函数）：为了找到最小的满足条件的m，低位匹配的m中，值最小的节点优先展开。

程序说明：节点node的成员变量说明如下：

curr：当前低位匹配的m值；

len：当前已经匹配的位数；

digit：当前位正在试探的数字（0-9）。

AC的C++语言程序如下：

/* HDU4394 Digital Square */#include 
    
     #include 
     
      using namespace std;typedef unsigned long long ULL;const int MAXN = 18;const int MAXDIGIT = 9;struct node {    ULL curr;    int len, digit;    node(){}    node(ULL c, int l, int n):curr(c), len(l), digit(n){}    bool operator<(const node n) const {        return curr > n.curr;    }};node start;int n;ULL fact[18];int nlen;ULL ans;void bfs(){    nlen = 0;    ULL temp = n;    while(temp) {        nlen++;        temp /= 10;    }    ans = 0;    priority_queue
      
        q;    q.push(node(0, 0, 0));    while(!q.empty()) {        node top = q.top();        q.pop();        if(top.len == nlen) {            ans = top.curr;            break;        } else if(top.digit != MAXDIGIT)            q.push(node(top.curr, top.len, top.digit+1));        node v;        v.curr = top.curr + fact[top.len] * top.digit;        v.len = top.len + 1;        v.digit = 0;        if(v.curr * v.curr % fact[v.len] == n % fact[v.len])            q.push(v);    }}int main(){    int t;    fact[0] = 1;    for(int i=1; i
       
        > t;    while(t--) {        cin >> n;        bfs();        if(ans)            printf("%llu\n", ans);        else            printf("None\n");    }    return 0;}