HDU 4394 Digital Square [搜索]

　　求最小的尾数为X的平方数。　　

　　符合情况的数不会有太多，从后向前搜就可以了。

 1 #include <string.h>
 2 #include <stdio.h>
 3 #include <algorithm>
 4 #define INF 0x3fffffff
 5 typedef long long LL;
 6 int cas,n,num[15],len,ans;
 7 LL sqr(int x){
 8     return (LL)x*x;
 9 }
10 void dfs(int l,int mul,int pre){
11     if(l==len){
12         ans=std::min(pre,ans);
13         return;
14     }
15     for(int i=0;i<10;i++){
16         if(sqr(i*mul+pre)/mul%10==num[l]){
17             dfs(l+1,mul*10,i*mul+pre);
18         }
19     }
20 }
21 int main(){
22     //freopen("test.in","r",stdin);
23     for(scanf("%d",&cas);cas--;){
24         scanf("%d",&n);
25         len=0;
26         while(n)num[len++]=n%10,n/=10;
27         ans=INF;
28         dfs(0,1,0);
29         if(ans!=INF)printf("%d\n",ans);
30         else printf("None\n");
31     }
32     return 0;
33 }