Digital Square

Time Limit : 2000/1000ms (Java/Other) Memory Limit : 32768/32768K (Java/Other)

Total Submission(s) : 10 Accepted Submission(s) : 6

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[sup]9[/sup]), 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

 

簡單搜索題，判斷幾位數相乘後對余數沒有影響就好

 

 

#include
#include
#include
#include
using namespace std;

int t,n;
long long Mod;

struct node
{
    long long num;
    long long ten;
    friend bool operator < (node a,node b)
    {
        return a.num>b.num;
    }
} a,b;

void bfs()
{
    priority_queueq;
    int num=n%10;
    for(int i=0; i<10; i++)
        if(i*i%10==num)
        {
            a.num=i;
            a.ten=10;
            q.push(a);
        }
    while(q.size())
    {
        a=q.top();
        if(a.num*a.num%Mod==n)
        {
            cout<>n;
        int nn=n;
        Mod=1;
        while(nn)
        {
            Mod*=10;
            nn/=10;
        }
        bfs();
    }
}