M2%10x=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;
}