【HDU 4394】Digital Square（bfs，数位搜索，思维，数学）

题干：

Given an integer N,you should come up with the minimum nonnegative integer M.M meets the follow condition: M 2%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 9), 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

题目大意：

解题报告：

N的个位只由M的个位决定，N十位由M的个位和十位决定，N的百位由M的个位十位百位决定，以此类推。

所以可以直接bfs优先队列式搜索，先确定个位，再确定十位，再确定百位，以此类推，因为N的范围是1e9，所以M也可以直接在1e9范围内搜索，因为当前搜索的那一位如果不满足的话就不会入队，所以不需要加其他的break条件就可以结束bfs。

AC代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cmath>
#include<cstring>
#define F first
#define S second
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
typedef pair<int,int> PII;
const int MAX = 2e5 + 5;
struct Node {
	ll val,step;
	Node(ll val=0,ll step=0):val(val),step(step){}
	bool operator < (const Node & b)const {
		return val>b.val;
	}
};
ll bfs(ll n) {
	priority_queue<Node> pq;
	pq.push(Node(0,1));
	while(!pq.empty()) {
		Node cur = pq.top();
		pq.pop();
		if((cur.val*cur.val)%cur.step == n) return cur.val;
		Node now = cur;
		now.step *= 10;
		for(ll i = 0; i<10; ++i) {
			now.val = cur.val+i*cur.step;
			if((now.val*now.val)%now.step == n%now.step) {
				pq.push(now);
			}
		}
	}
	return -1;
}

int main() {
	int t;
	scanf("%d",&t);
	while(t--) {
		ll n;
		scanf("%lld",&n);
		ll ans = bfs(n);
		if(ans == -1) puts("None");
		else printf("%lld\n",ans);
	}
	return 0;
}