子字符串整除问题 | 欧拉项目 | 43题

欧拉项目上的第43题：
数字1406357289是由0-9组成的，说明是一个pandigital number（全位数？）。除此之外，它还有一个很好的性质，描述如下：
设d1是第一个数字，d2是第二个数字，以此类推。有以下整除性质：

d2d3d4=406 is divisible by 2  
d3d4d5=063 is divisible by 3  
d4d5d6=635 is divisible by 5  
d5d6d7=357 is divisible by 7  
d6d7d8=572 is divisible by 11  
d7d8d9=728 is divisible by 13  
d8d9d10=289 is divisible by 17

问题是，求所有满足这种性质的pandigital number之和。

一开始，想了一个最直接的想法，找到所有的pandigital number，其实就是一个全排列算法，然后从里面过滤出满足性质的数字，最后求和。算法复杂度正比于9 * 9!！
本地实验了一下，150秒左右得到了正确的结果。不过，网站上有说明，算法足够好，小于1分钟。虽然我能使用C#自带的并行库提高性能，但毕竟不是修改了算法。

后来我发现，若干位整除是独立开的，那么，可以一步一步构造数字，比如先找到3位数字里面满足整除17要求的数字，在上一步的基础上，最前面添加一位数字，再要求整除13，以此类推，最后得到整个数字。需要8次迭代，但是每次的结果集都非常小，所以速度非常快，一瞬间就能得到想要的结果。

下面是写代码。首先定义了数字这个数组：

1	var digits = new string[] { "0", "1", "2", "3", "4", "5", "6", "7", "8", "9" };

找到能够整除17的。最后的ToArray方法必须调用一下，这样能得到子集。如果不调用这个方法，只是一个query语句，并没有执行。而我多次利用这个东西，最后结果就是把query拼接起来再一起执行，恩，复杂度超高，估计计算机算不出来，然后抛异常。

var d3 = (from i in digits
          from j in digits
          from k in digits
          select i + j + k).Where(IsPandigital).Where(s => int.Parse(s) % 17 == 0).ToArray();

接着，往前面添加一个数字，使之成为4位数，同时，筛选出指定三位能整除13的数字：

1
2
3

var d4 = (from i in digits
          from n in d3
          select i + n).Where(IsPandigital).Where(s => int.Parse(s.Substring(0, 3)) % 13 == 0).ToArray();

下面是以此类推，最后拼接出满足条件的10位数：

var d5 = (from i in digits
          from n in d4
          select i + n).Where(IsPandigital).Where(s => int.Parse(s.Substring(0, 3)) % 11 == 0).ToArray();

var d6 = (from i in digits
          from n in d5
          select i + n).Where(IsPandigital).Where(s => int.Parse(s.Substring(0, 3)) % 7 == 0).ToArray();

var d7 = (from i in digits
          from n in d6
          select i + n).Where(IsPandigital).Where(s => int.Parse(s[2].ToString()) % 5 == 0).ToArray();

var d8 = (from i in digits
          from n in d7
          select i + n).Where(IsPandigital).Where(s => int.Parse(s.Substring(0, 3)) % 3 == 0).ToArray();

var d9 = (from i in digits
          from n in d8
          select i + n).Where(IsPandigital).Where(s => int.Parse(s[2].ToString()) % 2 == 0).ToArray();

var d10 = (from i in digits
           from n in d9
           select i + n).Where(IsPandigital).Where(s => s[0] != 0).ToArray();

最后，我们返回和：

1	return d10.Select(s => long.Parse(s)).ToArray().Sum();

Where中使用的方法如下，作用是判断一个数是否是pandigital number：

private static bool IsPandigital(string s)
{
    return s.Length == s.ToArray().Distinct().Count();
}