M²%10^x=N
(x=0,1,2,3....)

给出N。找到最小的满足条件的M

因为：N的个位仅仅由M的个位决定。N十位由M的个位和十位决定，N的百位由M的个位十位百位决定。以此类推

全部从个位開始搜索满足条件的数字就可以

#include"stdio.h"

#include "string.h"

#include "math.h"

#include "queue"

using namespace std;

__int64  flag,n;

__int64  make(__int64  x,__int64  dit,__int64  num,__int64  i)

{

    __int64  y,now,j;

    y=1;

    for (j=1;j<dit;j++)

        y*=10;

    now=x+y*i;

    if ((now*now%(y*10)/y)==num) return now;

    return -1;

}

void bfs()

{

    queue<__int64>q;

    __int64  dit,i,cnt,x,now,num;

    q.push(0);

    dit=0;

    flag=-1;

    while (!q.empty())

    {

        cnt=q.size();

        num=n%10;

        dit++;

        n/=10;

        while (cnt--)

        {

            x=q.front();

            q.pop();

            for (i=0; i<=9; i++)

            {

                now=make(x,dit,num,i); // x之前所生成的数字，dit当前搜索到第几位，应该位应该匹配的数字，搜索当前位数字为i

                if (now!=-1)

                {

                    q.push(now);

                    if (n==0)

                    {

                        if (now<flag|| flag==-1)

                            flag=now;

                    }

                }

            }

        }

        if (flag!=-1) return ;

    }

}

int  main()

{

    __int64  t;

    scanf("%I64d",&t);

    while (t--)

    {

        scanf("%I64d",&n);

        if (n==0)

        {

            printf("0\n");

            continue;

        }

        bfs();

        if (flag==-1) printf("None\n");

        else printf("%I64d\n",flag);

    }

    return 0;

}