首页 > ACM题库 > HDU-杭电 > HDU 4394-Digital Square-数论-[解题报告]HOJ
2015
05-24

HDU 4394-Digital Square-数论-[解题报告]HOJ

Digital Square

问题描述 :

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….)

输入:

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.

输出:

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.

样例输入:

3
3
21
25

样例输出:

None
11
5

题目:Digital Square

 

题意:

Given an integer N,you should come up with the minimumnonnegative integer M.M meets the follow condition: M2%10x=N (x=0,1,2,3….)
 
 

从低位向高位广搜,如果当前情况满足M^2 % 10^y = N % 10^y,则继续向下搜索。


#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
const __int64 INF = 100000000000LL;

struct Node
{
    __int64 m, x;
    Node()
    {
        m = 0;
        x = 0;
    }
};

__int64 ten[10];

void init()
{
    __int64 num = 1;
    for(int i=0;i<10;++i)
    {
        ten[i] = num;
        num *= 10;
    }
}

int getLength(__int64 x)
{
    if(x == 0) return 1;
    int len = 0;
    while(x > 0)
    {
        x /= 10;
        ++ len;
    }
    return len;
}

int main()
{
    int caseNumber;
    __int64 n;
    init();
    scanf("%d", &caseNumber);
    while(caseNumber--)
    {
        scanf("%I64d", &n);
        int len = getLength(n);
        queue<Node> q;
        q.push(Node());
        while(!q.empty())
        {
            Node u = q.front();
            if(u.x == len) break;
            for(int i=0;i<10;++i)
            {
                Node v;
                v.m = u.m + ten[u.x] * i;
                v.x = u.x + 1;
                if((v.m * v.m) % ten[v.x] == n % ten[v.x]) q.push(v);
            }
            q.pop();
        }
        __int64 ans = INF;
        while(!q.empty())
        {
            Node node = q.front();
            if(ans > node.m)
                ans = node.m;
            q.pop();
        }
        if(ans == INF) printf("None\n");
        else           printf("%I64d\n", ans);
    }
    return 0;
}

 

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/acdreamers/article/details/9000388