题目描述

Carryless addition is the same as normal addition, except any carries are ignored (in base 10). Thus,  37  +  48  is  75,  not  85.  
Carryless multiplication is performed using the schoolbook algorithm for multiplication, column by column, but the intermediate sums are calculated using carryless addition. Thus:  
9 ∙ 1234 = 9000 + (900 + 900) + (90 + 90 + 90) + (9 + 9 + 9 + 9)   = 9000 + 800 + 70 + 6 = 9876   90 ∙ 1234 = 98760   99 ∙ 1234 = 98760 + 9876 = 97536  
Formally, define  ck to be the  kth digit of the value c. If  c = a·b  then  
***
Given an integer  n , calculate the smallest positive integer  a  such that  a∙a=n  in carryless multiplication. 

输入

The input consists of a single line with an integer n ( 1 ≤n ≤ 1025 ). 

输出

Output the smallest positive integer that is a carryless square root of the input number, or  − 1 if no such number exists. 

样例输入 

【样例1】
6 
【样例2】
149 
【样例3】 
123476544
【样例4】
15 

样例输出 

【样例1】
4
【样例2】
17 
【样例3】 
11112
【样例4】
-1

描述：
题目规则是算出这一位上的数字后只保留个位，给定一个数x，求出一个数y，使得y * y在题目规则下等于x
思路：
由于数据只有25位，可以考虑直接枚举每一位上的数字，每一次枚举后计算平方，然后比较看是不是和原数x相等，不相等就返回，相等就枚举下一位。
代码：

#include <iostream>
#include <cstring>
 
using namespace std;
 
const int N = 30;
 
int a[N], s[N], r[N];
int n;
 
void dfs(int u)
{
    if (u == n)
    {
        memset(s, 0, sizeof s);
         
        for (int i = 0; i < n; i ++ )
            for (int j = 0; j < n; j ++ )
            {
                s[i + j] += a[i] * a[j];
                s[i + j] %= 10;
            }
             
        for (int i = 0; i < n * 2 - 1; i ++ )
            if (s[i] != r[i]) return;
 
        for (int i = 0; i < u; i ++ )
            printf("%d", a[i]);
             
        exit(0);
    }
     
    for (int i = 0; i <= 9; i ++ )
    {
        a[u] = i;
        memset(s, 0, sizeof s);
        for (int j = 0; j <= u; j ++ )
            for (int k = 0; k <= u; k ++ )
            {
                if (j + k > u) break;
                s[j + k] += a[j] * a[k];
                s[j + k] %= 10;
            }
             
        bool flag = true;
        for (int j = 0; j <= u; j ++ )
            if (r[j] != s[j])
            {
                flag = false;
                break;
            }
             
        if (flag) dfs(u + 1);
    }
}
 
int main()
{
    string x;
    cin >> x;
    for (int i = 0; i < x.size(); i ++ )
        r[i] = x[i] - '0';
         
    n = (x.size() + 1) / 2;
 
    if (!(x.size() & 1)) puts("-1");
    else
    {
        dfs(0);
        puts("-1");
    }
     
    return 0;
}