Problem43 独特な部分列被整除性を持つPandigital数

問題

数1406357289は0から9のPandigital数である (0から9が1度ずつ現れるので).
この数は部分列が面白い性質を持っている.

d1を1桁目, d2を2桁目の数とし, 以下順にdnを定義する.
この記法を用いると次のことが分かる.

d2 d3  d4=406は2で割り切れる
d3 d4  d5=063は3で割り切れる
d4 d5  d6=635は5で割り切れる
d5 d6  d7=357は7で割り切れる
d6 d7  d8=572は11で割り切れる
d7 d8  d9=728は13で割り切れる
d8 d9 d10=289は17で割り切れる
このような性質をもつ0から9のPandigital数の総和を求めよ.

ソース

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        var Stk = new Stack<string>();
        for (int I = 1; I <= 9; I++)
            Stk.Push(I.ToString());

        long Answer = 0;
        while (Stk.Count > 0) {
            string Popped = Stk.Pop();
            if (Popped.Length == 10) {
                Answer += Convert.ToInt64(Popped);
                Console.WriteLine("{0}は、条件を満たすPandigital数", Popped);
            }

            for (int I = 0; I <= 9; I++) {
                if (Popped.Contains(I.ToString()) == false) {
                    string WillPush = Popped + I.ToString();
                    if (WillEdakiri(WillPush) == false) {
                        Stk.Push(WillPush);
                    }
                }
            }
        }
        Console.WriteLine("答えは、{0}", Answer);
    }

    static bool WillEdakiri(string pTarget)
    {
        int Length = pTarget.Length;
        if (Length == 4) return (int.Parse(pTarget.Substring(1, 3)) % 2) != 0;
        if (Length == 5) return (int.Parse(pTarget.Substring(2, 3)) % 3) != 0;
        if (Length == 6) return (int.Parse(pTarget.Substring(3, 3)) % 5) != 0;
        if (Length == 7) return (int.Parse(pTarget.Substring(4, 3)) % 7) != 0;
        if (Length == 8) return (int.Parse(pTarget.Substring(5, 3)) % 11) != 0;
        if (Length == 9) return (int.Parse(pTarget.Substring(6, 3)) % 13) != 0;
        if (Length == 10) return (int.Parse(pTarget.Substring(7, 3)) % 17) != 0;
        return false;
    }
}

実行結果

4160357289は、条件を満たすPandigital数
4130952867は、条件を満たすPandigital数
4106357289は、条件を満たすPandigital数
1460357289は、条件を満たすPandigital数
1430952867は、条件を満たすPandigital数
1406357289は、条件を満たすPandigital数
答えは、16695334890

解説

枝切りしながら深さ優先探索してます。