Digital Square
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1827 Accepted Submission(s):
714
Problem DescriptionGiven 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….) InputThe 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. OutputFor each case output the answer if it exists, otherwise
print “None”. Sample Input332125 Sample OutputNone115 Source2012
Multi-University Training Contest 10 Recommendzhuyuanchen520 | We have carefully selected several
similar problems for you: 4390 4398 4397 4396 4395 搜索题,首先证明出N位后缀只与M的后N位有关。比如三位数100a+10b+c平方后展开为 10000a^2+2000ab+100b^2+200ac+20bc+c^2很显然,平方后的最后一位只与c有关最后两位只与bc有关,最后三位abc都有关。那我们只需要BFS一下,不断地找满足最后指定位数的数,1位,2位,……直到找到第一个满足条件的。 题意:给出n,求出最小的m,满足m^2 % 10^k = n,其中k=0,1,2 附上代码:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
using namespace std;
__int64 n;
struct node
{
__int64 a;
int x;
friend bool operator < (node n1,node n2) //优先队列,必须输出最小的数
{
return n1.a>n2.a;
}
} s1,s2; void BFS()
{
priority_queue <node> q;
while(!q.empty())
q.pop();
__int64 t;
s1.a=;
s1.x=;
q.push(s1);
while(!q.empty())
{
s1=q.top();
q.pop();
t=(__int64)pow(10.0,s1.x); //从低位向高位搜
if(s1.a*s1.a%t==n) //找到了就直接输出
{
printf("%I64d\n",s1.a);
return;
}
for(int i=; i<; i++)
{
s2.x=s1.x+; //每次都向前进一位
s2.a=s1.a+i*t;
if(s2.a*s2.a%(t*)==n%(t*)) //一位一位的匹配,匹配成功后,则放入队列
q.push(s2);
}
}
printf("None\n");
}
int main()
{
int T,m,i,j;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
if(n%==||n%==||n%==||n%==) //根据乘法的规律,任何一个数平方后的个位数不可能是这些数
{
printf("None\n");
continue;
}
BFS();
}
return ;
}