题目大意：乘法加法运算时不进位（进位舍去），给出一个数，这个数是一个数的平方运算而来的，求这个数。
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 ",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 ");///平方数的结果都不可能出现2,3,7,8 67 else if( a[0]=='2' || a[0]=='3' || a[0]=='7' || a[0]=='8' ) printf("-1 "); 68 else if( !len&1 ) printf("-1 ");///由于不进位,所以任何数的平方数的位数都为奇数 69 else{ 70 n=(len+1)/2; 71 dfs(0); 72 printf("-1 "); 73 } 74 return 0; 75 }