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数の総和を求めよ.

ソース

#include <stack>
#include <string>
#include <Windows.h>

bool IsEdakiri(std::string pTarget);

void main()
{
    std::stack<std::string> stk;

    for (int I=0;I<=9;I++){
        char wkCharArr[10];wsprintf(wkCharArr,"%d",I);
        stk.push(wkCharArr);
    }

    __int64 Answer = 0;
    while(stk.empty() == false){
        std::string Popped = stk.top(); stk.pop();
        if(Popped.size() == 10) {
            Answer += _atoi64(Popped.c_str());
            printf("%sは、条件を満たすPandigital数\n",Popped.c_str());
        }

        for (int I = 0; I <= 9; I++) {
            char wkCharArr[10];wsprintf(wkCharArr,"%d",I);
            if(Popped.find(wkCharArr) == std::string::npos){
                std::string WillPush = Popped + wkCharArr;
                if (IsEdakiri(WillPush) == false) {
                    stk.push(WillPush);
                }
            }
        }
    }
    printf("答えは、%I64d\n", Answer);
}

bool IsEdakiri(std::string pTarget)
{
    int Size = pTarget.size();
    if (Size == 4)  return (atoi(pTarget.substr(1,3).c_str()) % 2) != 0;
    if (Size == 5)  return (atoi(pTarget.substr(2,3).c_str()) % 3) != 0;
    if (Size == 6)  return (atoi(pTarget.substr(3,3).c_str()) % 5) != 0;
    if (Size == 7)  return (atoi(pTarget.substr(4,3).c_str()) % 7) != 0;
    if (Size == 8)  return (atoi(pTarget.substr(5,3).c_str()) % 11) != 0;
    if (Size == 9)  return (atoi(pTarget.substr(6,3).c_str()) % 13) != 0;
    if (Size == 10) return (atoi(pTarget.substr(7,3).c_str()) % 17) != 0;
    return false;
}

実行結果

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

解説

枝切りしながらの深さ優先探索を行ってから、
printf関数の書式指定でI64dを使用してます。(__int64型のため)

MSDN --- printf関数の書式指定