Digital Square
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 1757 Accepted Submission(s): 677
Problem Description
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....)
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 <=109), indicating the given number.
For each case, each line contains one integer N(0<= N <=109), indicating the given number.
Output
For each case output the answer if it exists, otherwise print “None”.
Sample Input
332125
Sample Output
None115
Source
2012 Multi-University Training Contest 10
Recommend
zhuyuanchen520 | We have carefully selected several similar problems for you: 4390 4398 4397 4395 4393
ac代码
#include<stdio.h>#include<string.h>#define INF 1<<30#define max(a,b) (a>b?a:b)#define min(a,b) (a>b?b:a)int a[20];__int64 mod[20],ans,n,len;void init(){ mod[0]=1; for(int i=1;i<20;i++) { mod[i]=mod[i-1]*10; }}void fun(){ __int64 temp=n; len=0; memset(a,0,sizeof(a)); while(temp) { a[len++]=temp%10; temp/=10; }}void dfs(int now,int step){ if(step==len) { ans=min(ans,now); return; } for(int i=0;i<=9;i++) { __int64 to,temp=now+mod[step]*i; to=temp; temp*=temp; temp/=mod[step]; temp%=10; if(temp==a[step]) { dfs(to,step+1); } }}int main(){ int t; init(); scanf("%d",&t); while(t--) { scanf("%I64d",&n); fun(); ans=INF; dfs(0,0); if(ans==INF) { printf("None\n"); } else printf("%d\n",ans); }}