题目大意：乘法加法运算时不进位（进位舍去），给出一个数，这个数是一个数的平方运算而来的，求这个数。
AC_Code
1 #include <bits/stdc++.h>
2 #include <cstdio>
3 #include <cstring>
4 #include <cmath>
5 #include <ctime>
6 #include <string>
7 using namespace std;
8
9 typedef long long ll;
10 const int maxn = 35;
11 int a[maxn], ans[maxn], d[maxn];
12 int n;
13 char s[maxn];
14
15 void dfs(int now_digit){
16 if( now_digit==n ){
17 memset(d,0,sizeof(d));
18 for(int j=0; j<now_digit; j++){
19 for(int k=0; k<now_digit; k++){
20 d[j+k]+=(ans[j]*ans[k]);
21 d[j+k]%=10;
22 }
23 }
24
25 for(int i=0;i<2*now_digit-1;i++){
26 if( d[i]!=a[i] ) return ;
27 }
28
29 for(int i=0;i<n;i++){
30 if( i==n-1 ) printf("%d\n",ans[n-1]);
31 else printf("%d",ans[i]);
32 }
33 exit(0);
34 }
35
36 else{
37 for(int i=0; i<=9; i++){///注意为什么从0开始记位,而不从1开始记位,
38 ///因为从一开始(1+1)==2,算出来没有第1位了
39 ans[now_digit] = i;
40 memset(d,0,sizeof(d));
41 for(int j=0; j<=now_digit; j++){
42 for(int k=0; k<=now_digit; k++){
43 if( j+k>now_digit ) break;
44 d[j+k]+=(ans[j]*ans[k]);
45 d[j+k]%=10;
46 }
47 }
48
49 int flag=0;
50 for(int ii=0;ii<=now_digit;ii++){
51 if( d[ii]!=a[ii] ) flag=1;
52 }
53 if( !flag ){///比较快,如果原来是flag==1,判flag==1,用了31ms,判!flag用了15ms
54 dfs(now_digit+1);
55 }
56 }
57 }
58 }
59
60 int main()
61 {
62 scanf("%s",s);
63 int len = strlen(s);
64
65 for(int i=0;i<len;i++) a[i]=s[i]-'0';
66 if( a[len-1]=='2' || a[len-1]=='3' || a[len-1]=='7' || a[len-1]=='8' ) printf("-1\n");///平方数的结果都不可能出现2,3,7,8
67 else if( a[0]=='2' || a[0]=='3' || a[0]=='7' || a[0]=='8' ) printf("-1\n");
68 else if( !len&1 ) printf("-1\n");///由于不进位,所以任何数的平方数的位数都为奇数
69 else{
70 n=(len+1)/2;
71 dfs(0);
72 printf("-1\n");
73 }
74 return 0;
75 }