Digital Square
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1882 Accepted Submission(s): 741
Problem Description
Given an integer N,you should come up with the minimum nonnegative integer M.M meets the follow condition: M2%10x=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 <=109), indicating the given number.
For each case, each line contains one integer N(0<= N <=109), 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
Source
解析：设M = abc，即M = 100*a+10*b+c，则M2 = 10000*a2 + 1000*2*a*b + 100*(b2+2*a*c) + 10*2*b*c + c2。易知，M2的个位只与M的最后1位有关，M2的十位只与M的最后2位有关，M2的百位只与M的最后3位有关……我们可以从个位开始进行广搜，逐位满足N。如果有可行解，找出这一层当中最小的解并输出；否则输出"None"。
#include <cstdio>
#include <queue>
using namespace std; struct node{
long long value,place;
}; void bfs(long long n)
{
node tmp;
tmp.value = ;
tmp.place = ;
queue<node> q;
q.push(tmp);
bool findans = false;
long long ans = 0xffffffff;
while(!q.empty()){
tmp = q.front();
q.pop();
node now;
now.place = tmp.place*;
for(int i = ; i<; ++i){
now.value = tmp.value+i*tmp.place;
if(now.value*now.value%now.place == n%now.place){
if(!findans)
q.push(now);
if(now.value*now.value%now.place == n && now.value<ans){
findans = true;
ans = now.value;
}
}
}
}
if(ans == 0xffffffff)
printf("None\n");
else
printf("%I64d\n",ans);
} int main()
{
int t;
scanf("%d",&t);
while(t--){
long long n;
scanf("%I64d",&n);
bfs(n);
}
return ;
}
上面的代码找到可行解之后需要进行比较找出最优解，我们可以对此进行优化，把queue改为priority_queue，让priority_queue帮我们完成这个工作，使得找到的第一个可行解便是满足题意的最优解。
#include <cstdio>
#include <queue>
using namespace std; struct node{
long long value,place;
bool operator < (const node& b)const
{
return value>b.value;
}
}; void bfs(long long n)
{
node tmp;
tmp.value = ;
tmp.place = ;
priority_queue<node> q;
q.push(tmp);
while(!q.empty()){
tmp = q.top();
q.pop();
if(tmp.value*tmp.value%tmp.place == n){
printf("%I64d\n",tmp.value);
return ;
}
node now;
now.place = tmp.place*;
for(int i = ; i<; ++i){
now.value = tmp.value+i*tmp.place;
if(now.value*now.value%now.place == n%now.place){
q.push(now);
}
}
}
printf("None\n");
} int main()
{
int t;
scanf("%d",&t);
while(t--){
long long n;
scanf("%I64d",&n);
bfs(n);
}
return ;
}