Digital Square

3
3
21
25

None
11
5

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);
	}
}

HDOJ 题目4394 Digital Square（DFS）

原文：http://blog.csdn.net/yu_ch_sh/article/details/44890631