Project Euler 719

题目

Number Splitting

We define an \(S\)-number to be a natural number, \(n\), that is a perfect square and its square root can be obtained by splitting the decimal representation of \(n\) into \(2\) or more numbers then adding the numbers.

For example, \(81\) is an \(S\)-number because \(\sqrt{81} = 8+1\).

\(6724\) is an \(S\)-number: \(\sqrt{6724} = 6+72+4\).

\(8281\) is an \(S\)-number: \(\sqrt{8281} = 8+2+81 = 82+8+1\).

\(9801\) is an \(S\)-number: \(\sqrt{9801}=98+0+1\).

Further we define \(T(N)\) to be the sum of all \(S\) numbers \(n\le N\). You are given \(T(10^4) = 41333\).

Find \(T(10^{12})\)

解决方案

对于\(n>1\)，永远不会出现\(n^2=n\)的情况，因此这里不需要判断一个正确的划分方案是否只有一个数（而不是多个数相加）。

另外一个优化之处则是只有当\(n\%9<2\)时，\(n^2\)才有可能是一个候选答案，原因：假设\(d\)是\(n\)的各位数字之和，那么无论等式右侧的数如何划分，它们的数位和模\(9\)和\(n^2\)的数位和模\(9\)是一样的。根据\(S\)数的定义，\(n\)和这些划分后的数位值相加相等，因此\(n^2\equiv n\pmod 9.\)

其余的部分则使用深度优先搜索对\(n\)进行判断，在判断的过程中，注意加法的每个项不可能超过\(n\).

代码

# include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const ll N=1e12;
ll m;
int a[25],p=0;
bool dfs(int f,ll s,ll w){
    if(s>m||w>m) return 0;
    if(f==p) return s+w==m;
    if(dfs(f+1,s+w,a[f])||dfs(f+1,s,w*10+a[f])) return 1;
    return 0;
}
int main(){
    ll ans=0;
    for(m=4;m*m<=N;m++){
        if(m%9>1) continue;
        ll t=m*m;
        p=0;
        for(;t;t/=10) a[p++]=t%10;
        reverse(a,a+p);
        if(dfs(0,0,0)) ans+=m*m;
    }
    printf("%lld\n",ans);
}