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；那么，我们的是不是就由(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[],num,n,ans,r,final;

ll min(ll a, ll b)

{

    return a > b? b : a;

}

void get(ll t) //得到num = n的位数，digit[]存每个位上分别是什么。

{

    num=;

    while(t)

    {

        digit[ ++num] = t % ;

        t/=;

    }

}

void solve(ll p,ll w,ll ans)

{

    if(p>num)

    {

        final=min(final,ans);

        return ;

    }

    for(ll k = ;k<;k ++)

    {

        if( (ans*ans/w + r*k%)%==digit[p])//(b * b / 10 + a * b * 2) % 10，，，r=2*ans

            solve(p+,w*,k*w+ans);

    }

}

int main()

{

    scanf("%I64d",&t);

    while(t--)

    {

        scanf("%I64d",&n);

        get(n);

        if(digit[]==||digit[]==||digit[]==||digit[]==)

        {

            puts("None");

            continue;

        }

        final = INF;

        for(ll i=;i<;i++)

        {

            if(i*i%==digit[])

            {

                r=i<<;   //r为余数2*ans

                solve(,,i);

            }

        }

        if(final==INF)

            puts("None");

        else

            printf("%I64d\n",final);

    }

    return ;

}

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

只是时间问题。

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<queue>

 #include<cmath>

 using namespace std;

 typedef __int64 ll;

 struct Node

 {

     ll num;

     int len;//长度

     bool operator < (const Node &p) const

     {

         return p.num<num;

     }

 };

 ll n,ans;

 ll kpow(int x)

 {

     ll kk=;

     for(int i=;i<x;i++)

         kk=kk*;

     return kk;

 }

 bool bfs()

 {

     priority_queue<Node>Q;

     Node p,q;

     p.num=,p.len=;

     Q.push(p);

     while(!Q.empty())

     {

         p=Q.top();

         Q.pop();

         ll tmp=kpow(p.len);

         if(p.num*p.num%tmp==n)

         {

             ans=p.num;

             return true;

         }

         //扩展

         for(int i=; i<; i++)

         {

             q.len=p.len+;

             q.num=p.num+i*tmp;

             if(q.num*q.num%(tmp*)==n%(tmp*))

                 Q.push(q);

         }

     }

     return false;

 }

 int main()

 {

     int T;

     scanf("%d",&T);

     while(T--)

     {

         scanf("%I64d",&n);

         int temp=n%;

         if(temp==||temp==||temp==||temp==)

         {

             puts("None");

             continue;

         }

         if(bfs())

             printf("%I64d\n",ans);

         else

             puts("None");

     }

     return ;

 }

巴特西

Digital Square（hdu4394）搜索

Digital Square

最新文章

热门文章