HDU(4394)，数论上的BFS

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

思路很巧妙，要找到m,可以这样思考，n的个位是有m的个位决定的，从0-9搜一遍，满足情况的话就继续搜索m的十位，这里的状态转移可以利用之前的m，因为m是在m的自身上增加的，这时，其实个位是已经满足情况了，而且，n的个位，十位，百位等等是很难单独取出来的，所以就直接取完后面的全部数字。

#include <stdio.h>
#include <queue>
#include <math.h>

using namespace std;

struct NUM
{
    long long num;
    int len;
    bool operator < (const NUM &a) const
    {
        return a.num < num;
    }
};



int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        priority_queue<NUM> Q;
        int n;
        scanf("%d",&n);

        NUM a,next;

        a.len = 0;
        a.num = 0;
        Q.push(a);
        bool flag = false;
        while(!Q.empty())
        {
            a = Q.top();
            Q.pop();

            if(a.num*a.num%(int)pow(10,a.len)==n)
            {
                flag = true;
                break;
            }
            a.len++;
            for(int i=0; i<=9; i++)
            {
                next = a;
                next.num +=i*(int)pow(10,a.len-1);
                //printf("%d %d
",next.num,next.len);
                //printf("%d %d
",next.num*next.num%(int)pow(10,next.len),n%(int)pow(10,next.len));
                if(next.num*next.num%(int)pow(10,next.len)==n%(int)pow(10,next.len))
                    Q.push(next);
            }
        }
        if(flag)
            printf("%d
",a.num);
        else printf("None
");
    }
    return 0;
}