719 Number Splitting
首先来定义什么是 -number。若一个自然数 是完全平方数，且将 的十进制写法分割成 2 个或多个数字，这些数字之和恰好是其平方根，那么这个数字就是 -number。
以下都是-number： * * * *
表示所有 的 -number 之和。已知 。求 。
遍历 ，可以得到所有 的候选值，这些数可能的 -number，需要考虑的就是如何判断一个根 和 满足 -number 的性质。
首先，对于某个 ，其长度是 ，那么分割的方式总是固定的。比如 和 的分割模式是一致的，前者分别是 ，后者分别是 。那么遍历出所有模式，长度最多是 12。 长度是 13，但是它是 -number 先不考虑，最后求和加上就行。
private static List<Pattern> GetAllPatternsByLength(int length)
{
var result = new List<Pattern>() { new Pattern().AddPair(Tuple.Create(0, length)) };
for (int i = 1; i < length; i++)
{
var subPatterns = GetAllPatternsByLength(length - i);
result.AddRange(subPatterns.Select(pattern => pattern.AddOffset(i).AddPair(Tuple.Create(0, i))));
}
return result;
}
class Pattern
{
// (start, length)
public List<Tuple<int, int>> Pairs { get; private set; }
private int max;
public Pattern()
{
Pairs = [];
}
public Pattern AddPair(Tuple<int, int> pair)
{
Pairs.Add(pair);
if (pair.Item2 > max)
{
max = pair.Item2;
}
return this;
}
public Pattern AddOffset(int offset)
{
var result = new Pattern();
foreach (var pair in Pairs)
{
result.AddPair(Tuple.Create(pair.Item1 + offset, pair.Item2));
}
return result;
}
public int GetMaxLength()
{
return max;
}
}
和 之间是有一些关系的，比如 长度是 6，而 可能是 11 也可能是 12。不过若长度是 12，那么 首字母会大于等于 3，如果分割的数字最长的长度小于 6 的话，那么两个五位数再加一个两位数，是不会得到一个以 3 开头的数字的。对于 的长度是 11 的情况，最长的被分割数字也不能太短，最短也要五位数字。所有可以通过这个过滤掉很多不必要的选项。由于这个性质之和 和 的长度有关，可以把结果缓存起来。
private List<Pattern> GetPatterns(int rootLength, int length)
{
string key = rootLength + "_" + length;
if (!mappings.ContainsKey(key))
{
if (rootLength * 2 == length)
{
mappings[key] = patterns[length].Where(p => p.GetMaxLength() == rootLength).ToList();
}
else
{
mappings[key] = patterns[length].Where(p => p.GetMaxLength() == rootLength || p.GetMaxLength() == rootLength - 1).ToList();
}
}
return mappings[key];
}
有了这些可能的值，就可以遍历这些可能的值来判断一个数字 是不是 -number。
private bool CanBeSplit(long root, long S)
{
int rootLength = (int)Math.Floor(Math.Log10(root) + 1);
int sLength = (int)Math.Floor(Math.Log10(S) + 1);
var patterns = GetPatterns(rootLength, sLength);
string strS = S.ToString();
foreach (var pattern in patterns)
{
int sum = 0;
foreach (var pair in pattern.Pairs)
{
sum += int.Parse(strS.Substring(pair.Item1, pair.Item2));
}
if (sum == root)
{
return true;
}
}
return false;
}
最外层遍历 即可。
for (int i = 2; i <= 12; i++)
{
patterns[i] = GetAllPatternsByLength(i);
}
long END = 1_000_000;
long sum = END * END;
// 1, 4, 9 cannot be split into 2 or more numbers
for (long i = 4; i < END; i++)
{
long S = i * i;
if (CanBeSplit(i, S))
{
sum += S;
}
}
return sum.ToString();
第一个是代码
这里耗时比较多，这里很容易通过数字的除法和求余来搞定，会快不少。private readonly long[] Pows = new long[] {1,10,100,1000, 10000,
100000, 1000000, 10000000,100000000,1000000000,
10000000000,100000000000,1000000000000};
sum += S / Pows[sLength - pair.Item1 - pair.Item2] % Pows[pair.Item2];
第二个是仔细考虑下
和 之间是有一些关系的，比如 长度是 6，而 可能是 11 也可能是 12。不过若长度是 12，那么 首字母会大于等于 3，如果分割的数字最长的长度小于 6 的话，那么两个五位数再加一个两位数，是不会得到一个以 3 开头的数字的。对于 的长度是 11 的情况，最长的被分割数字也不能太短，最短也要五位数字。所有可以通过这个过滤掉很多不必要的选项。
两者的判断标准可以更细致，如果 是的前两个数字大于等于 21，那么分割的数字最长的长度就必须等于 的长度，因为再小的话就无法加起达到 了。举个具体例子， 长度是 3，如果 的长度是 6，回到上一段的情况，若 的长度是 5，最长长度是 2，那么两个两位数和一个 1 位数，其和最大不可能是 210，而 是的前两个数字大于等于 21。改写这个判断逻辑，能够再减少一些不必要的模式。
while (root > 100)
{
root /= 10;
}
var t = root >= 21;
string key = rootLength + "_" + sLength + (t ? "T" : "F");
if (!mappings.ContainsKey(key))
{
if (t)
{
mappings[key] = patterns[sLength].Where(p => p.GetMaxLength() == rootLength).ToList();
}
else
{
mappings[key] = patterns[sLength].Where(p => p.GetMaxLength() == rootLength || p.GetMaxLength() == rootLength - 1).ToList();
}
}
第三个优化点是在求和那里，如果前面的几个数字之和已经超过了 ，就不要继续了。比如 ，前面三个数字超过了 212，不过后面怎么样，也无所谓了。
经过优化，在我机器上大概 13s 能得到答案。其实有一个方向，是第三点的扩展，各个模式恰好能组成一棵树，那么自上而下算到某个节点超过了 ，下面整个子树都不需要算了。但是构建这个树也要遍历所有的模式的每一个起始 pair，不好说最后能够提高性能。