HDU 4394 Digital Square

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: M²%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⁹), 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

2012 Multi-University Training Contest 10

解析：设M = abc，即M = 100*a+10*b+c，则M² = 10000*a² + 1000*2*a*b + 100*(b²+2*a*c) + 10*2*b*c + c²。易知，M²的个位只与M的最后1位有关，M²的十位只与M的最后2位有关，M²的百位只与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 ;
 }