Digital Square（hdu4394）搜索

Digital Square

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1310 Accepted Submission(s): 501

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

题意很简单 M²%10^x=N (x=0,1,2,3....)就不啰嗦了，

思路：

　　可以用dfs；（其实就是暴力+剪枝）

eg：n 为 21；那么，我们从个位数1开始搜， 1 * 1 = 1， 9 * 9 = 81，他们的个位数都是1，那么，1和9可以作为我们找的那个数的个位数。
然后我们就记忆一下这个我们找到的东西，放在ans里面。
下面我们开始搜第二位，设搜的是ab的a（其中，我们的b是已经记忆下来的个位）。
ab * ab % 100 = 21；那么，我们的2 是不是就由(b * b / 10 + a * b * 2) % 10 得到的（看不出来的可以拿纸笔算一下；）。未知数就只有a吧，那么，我们就for一遍去找a，找到a了，我们就以同样的方法去找c（如果有c的话）。这样，就是剪枝了。
最后，如果我们找的n有x位，那么，我们要找的m * m % ？ == n 的m最多也只有x位。至此，就结束了。

ps：http://acm.hdu.edu.cn/showproblem.php?pid=4394

详见代码

#include <cstdio>
#include<iostream>
#define INF 0xfffffff
#define ll __int64
using namespace std;


ll t,digit[20],num,n,ans,r,final;

ll min(ll a, ll b)
{
    return a > b? b : a;
}
void get(ll t) //得到num = n的位数，digit[]存每个位上分别是什么。
{
    num=0;
    while(t)
    {
        digit[ ++num] = t % 10;
        t/=10;
    }
}
void solve(ll p,ll w,ll ans)
{
    if(p>num)
    {
        final=min(final,ans);
        return ;
    }
    for(ll k = 0;k<10;k ++)
    {
        if( (ans*ans/w + r*k%10)%10==digit[p])//(b * b / 10 + a * b * 2) % 10，，，r=2*ans
            solve(p+1,w*10,k*w+ans);
    }
}
int main()
{
    scanf("%I64d",&t);
    while(t--)
    {
        scanf("%I64d",&n);
        get(n);
        if(digit[1]==2||digit[1]==3||digit[1]==7||digit[1]==8)
        {
            puts("None");
            continue;
        }
        final = INF;
        for(ll i=0;i<10;i++)
        {
            if(i*i%10==digit[1])
            {
                r=i<<1;   //r为余数2*ans
                solve(2,10,i);
            }
        }
        if(final==INF)
            puts("None");
        else
            printf("%I64d
",final);
    }
    return 0;
}

当然也可以不用这么麻烦直接dfs

只是时间问题。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<queue>
 5 #include<cmath>
 6 
 7 
 8 using namespace std;
 9 typedef __int64 ll;
10 
11 
12 
13 struct Node
14 {
15     ll num;
16     int len;//长度
17     bool operator < (const Node &p) const
18     {
19         return p.num<num;
20     }
21 };
22 ll n,ans;
23 
24 ll kpow(int x)
25 {
26     ll kk=1;
27     for(int i=0;i<x;i++)
28         kk=kk*10;
29     return kk;
30 }
31 bool bfs()
32 {
33     priority_queue<Node>Q;
34     Node p,q;
35     p.num=0,p.len=0;
36     Q.push(p);
37     while(!Q.empty())
38     {
39         p=Q.top();
40         Q.pop();
41         ll tmp=kpow(p.len);
42         if(p.num*p.num%tmp==n)
43         {
44             ans=p.num;
45             return true;
46         }
47         //扩展
48         for(int i=0; i<10; i++)
49         {
50             q.len=p.len+1;
51             q.num=p.num+i*tmp;
52             if(q.num*q.num%(tmp*10)==n%(tmp*10))
53                 Q.push(q);
54         }
55     }
56     return false;
57 }
58 
59 
60 int main()
61 {
62     int T;
63     scanf("%d",&T);
64     while(T--)
65     {
66         scanf("%I64d",&n);
67         int temp=n%10;
68         if(temp==2||temp==3||temp==7||temp==8)
69         {
70             puts("None");
71             continue;
72         }
73         if(bfs())
74             printf("%I64d
",ans);
75         else
76             puts("None");
77     }
78     return 0;
79 }

View Code