HDU-4394 Digital Square（DFS）

題目連結：http://acm.hdu.edu.cn/showproblem.php?pid=4394

Digital Square

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

Problem Description Given an integer N,you should 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, otherwise print “None”.  

Sample Input

3
3
21
25
        

Sample Output

None
11
5
        

數字n從個位開始的數字分别為n0,n1,n2……

模拟乘法運算，觀察可得：

n0=e^2%10

n1=(2*d*e+e^2/10)%10注意進位

n2=(2*c*e+d^2+(2*d*e+e^2/10)/10)%10

  =[2*c*e+(100*d^2+10*2*d*e+e^2)/100]%10

  ={2*c*e+[(de)^2]/100}%10

同理可得：n3,n4……

#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\n");
        else
            printf("%d\n",ans);
    }
    return 0;
}