HU-444 Digital Square(DFS)

テーマリンク:http://acm.hdu.edu.cn/showproblem.php?pid=4394
Digital Square
Time Limit:2000/1000 MS(Java/Others)    メモリLimit:32768/32768 K(Java/Others)
Problem Description
Gven an integer N,you Shou shoud come up with the minimum 
nonnegative integer M.M meets the follow condition:M
2%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
9)indicating the given number.
 
Output
For each case output the answer if it exists、other wise print“None”.
 
Sample Input

   
   
   
   

    
    
    
    3
3
21
25
   
   
   
   

 
Sample Output

   
   
   
   

    
    
    
    None
11
5
   
   
   
   

数字nは、ビットから始まる数字はそれぞれn 0,n 1,n 2…
乗算をシミュレートします.
n 0=e^2%10
n 1=(2**e+e^2/10)%10進数に注意
n 2=(2＊c*e+d^2+(2*d*e+e^2/10)%10
  =[2＊c＊e+(100＊d^2+10*2*d*e+e^2)/100]%10
  =｛2**e+[(de)^2]/100｝%10
同道理可得:n 3,n 4…

#include <cstdio>
#include <cstring>
#include <algorithm>
//#define LOCAL
using namespace std;

const __int64 INF=1<<30;

__int64 n,ans;
int len,m;
int num[10];
void DFS(__int64 pre,__int64 temp,int pos)//①pre=10^pos,    ②temp          pos   ③pos   pos  
{
    if(len==pos)
    {
        ans=min(ans,temp);
        return;
    }
    for(int i=0;i<=9;++i)
    {
        if(num[pos]==(temp*temp/pre+m*i%10)%10)//   pos    ，      
            DFS(10*pre,temp+i*pre,pos+1);
    }
}

int main()
{
#ifdef LOCAL
freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);
#endif
    int T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%I64d",&n);
        __int64 temp=n;
        len=0;
        while(temp)//  n      
        {
            num[len++]=temp%10;
            temp/=10;
        }
        ans=INF;//       
        for(int i=0;i<=9;++i)
            if(num[0]==i*i%10)
            {
                m=2*i;
                DFS(10,i,1);
            }
        if(ans==INF)
            printf("None
");
        else
            printf("%d
",ans);
    }
    return 0;
}