New Maths dfs

New Maths dfs

题目大意：

给你一个长度最多25一个数字 (n)，定义一种不进位的乘法，问是否有一个数满足：(x*x=n)

不进位乘法：

题解：

直接 (dfs) 就好，枚举每一个位置所有的可能，然后dfs判断即可

注意写法，我第一发写的及其的恶心。。。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5+10;
char s[100];
int up[100],ans[maxn],a[maxn],n,bit;
bool dfs(int u){
    if(u>n) return true;
    for(int i=0;i<=up[u];i++){
        ans[u] = i;
        int sum = 0;
        for(int j=1;j<=u;j++){
            sum += ans[j]*ans[u+1-j];
        }
        sum%=10;
//        printf("u = %d i = %d a[%d]=%d sum = %d
",u,i,u,a[u],sum);
        if(sum==a[u]){
            if(dfs(u+1)) return true;
        }
    }
    return false;
}
int main(){
    scanf("%s",s+1);
    n = strlen(s+1),bit = (n+1)/2;
    for(int i=1;i<=n;i++){
        a[i] = s[i] - '0';
        if(i<=bit) up[i] = 9;
        else up[i] = 0;
    }
    bool flag = dfs(1);
    if(!flag) printf("-1
");
    else {
        for(int i=1;i<=bit;i++) printf("%d",ans[i]);
        printf("
");
    }
}