Digital Square 搜索

Digital Square

Time Limit:1000MS Memory Limit:32768KB 64bit IO Format:%I64d & %I64u

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

Sample Output

None

 #include <iostream>

 #include <stdio.h>

 #include <set>

 #include <string.h>

 #include <algorithm>

 #include <queue>

 using namespace std;

 #define ll long long

 ll n,nu,ans;

 void init()

 {

     ll nn=n;

     nu=;

     while(nn)

     {

         nn/=;

         nu*=;

     }

 }

 bool fun()

 {

     int i,ok=;

     ans=n;

     ll now,x,y,noww;

     queue<pair<ll,ll> >q;

     while(!q.empty())

     q.pop();

     q.push(make_pair(,));

     while(!q.empty())

     {

         x=q.front().first;

         now=q.front().second;

         noww=now*;

         q.pop();

         for(i=;i<;i++)

         {

             y=x+now*i;

             if(y*y%nu==n){ans=min(ans,y);ok=;}

             else

             if(y*y%noww==n%noww)q.push(make_pair(y,noww));

         }

     }

     if(ok)return ;

     return ;

 }

 int main()

 {

     int t;

     scanf("%d",&t);

     while(t--)

     {

         cin>>n;

         if(n==)

         {

             cout<<<<endl;

             continue;

         }

         init();

         if(fun())

         {

             cout<<ans<<endl;

         }

         else printf("None\n");

     }

 }

巴特西

Digital Square 搜索

最新文章

热门文章