首页 > 代码库 > Digital Square（hdu4394）搜索

Digital Square（hdu4394）搜索

2024-07-16 11:26:49   227人阅读

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: M2%10x=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 <=109), 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
 
题意很简单 M2%10x=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 __int64using 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\n",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 Node14 {15     ll num;16     int len;//长度17     bool operator < (const Node &p) const18     {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\n",ans);75         else76             puts("None");77     }78     return 0;79 }
View Code

 

 

 


联系
我们