Digital Square(hdu 数论 4394，bfs求后n位相同)

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 462 Accepted Submission(s): 225

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

Sample Output

None

Source

Recommend

zhuyuanchen520

思路转自某神，，，看了才会的，，，，哎。。。。。继续加油！

M^2%10^x=N (x=0,1,2,3....),给你一个N，求M，x为0,1,2,3....其中一个数就行了。找不到M输出None

也就是求N是某个数的平方的后缀（包括本身）。

思路：

BFS。

首先证明出N位后缀只与M的后N位有关。

比如三位数100a+10b+c平方后展开为

10000a^2+2000ab+100b^2+200ac+20bc+c^2

很显然，平方后的最后一位只与c有关

最后两位只与bc有关，最后三位abc都有关

可以类推出上面的结论。

然后从个位开始广搜，逐位满足N, 每扩展

要判断一次是否为解。（有可能后面位数满足

的同时前面位数自动满足了）。注意有解时一

定要搜索这一层的所有解，输出最小解。

PS：要注意小细节如1000000000的情况，挂在这里好久。。。

View Code

1 #include
      
         2 #include
       
          3 #include
        
           4 #include
         
            5 #include
          
             6 #include
            7 #include
            
              8 #include
             
               9 #include
              
                10 #define M 200010 11 #define INF 2139062143 12 #define LL __int64 13 using namespace std; 14 15 class node 16 { 17 public: 18 int id; 19 LL num; //id是位置，从个位开始1,2.。。。num是这个id位数 20 node(int a,LL b) 21 { 22 id = a; 23 num = b; 24 } 25 }; 26 27 LL weishu(LL x) //求x是几位数 28 { 29 LL i = 1,j = 0; 30 while(x/i!=0) 31 { 32 i *= 10; 33 ++j; 34 } 35 36 return j; 37 } 38 39 bool eq(LL a,LL b,int k) //判断a和b的最后k位是否相同 40 { 41 while(k--) 42 { 43 if(a%10!=b%10) return false; 44 45 a = a/10; 46 b = b/10; 47 } 48 return true; 49 } 50 51 int main() 52 { 53 int i,T; 54 LL n; 55 queue
               
                q; 56 cin>>T; 57 while(T--) 58 { 59 LL ans = 0; 60 scanf("%I64d",&n); 61 62 while(!q.empty()) q.pop(); 63 bool flag = false; 64 int sumid = 0,j = 1; 65 sumid = weishu(n); 66 //cout<
                
                 <
                 
                   sumid) break; 94 if(iid == sumid) 95 { 96 if(k == n) 97 { 98 flag = true; 99 ans = k;100 break;101 }102 }103 104 for(i = 0;i<=9;i++)105 {106 LL dd = (i*pow(10,iid) + k),d = 0;107 d = dd*dd;108 if(eq(d,n,iid+1))109 {110 if(eq(d,n,sumid))111 {112 flag = true;113 ans = dd;114 for(;;)115 {116 if(q.empty()) break;117 int newiid = q.front().id;118 LL newk = q.front().num;119 q.pop();120 if(newiid!=iid) break;121 for(j = 1;j<=9;j++)122 {123 LL newdd = (j*pow(10,newiid) + newk),newd = 0;124 newd = newdd*newdd;125 if(eq(newd,n,sumid) && ans > newdd)126 {127 ans = newdd;128 }129 }130 }131 break;132 }133 // cout<