Project Euler - Problem 571

Super Pandigital Numbers

正の整数 n を b 進数で表したとき，0 から b - 1 までの全ての数字が少なくとも 1 回以上現れるとき，n は基数 b に関して pandigital であるという．

さらに，2 から n までの全ての基数で同時に pandigital である数を n-super-pandigital number と呼ぶ．
たとえば 978 = 1111010010₂ = 1100020₃ = 33102₄ = 12403₅ は，最小の 5-super-pandigital number である．
同様に，1093265784 は，最小の 10-super-pandigital number である．
小さい方から数えて 10 個の 10-super-pandigital number の合計は 20319792309 である．

小さい方から数えて 10 個の 12-super-pandigital number の合計はいくつか？

何のひねりもない方法で解いた．

12-pandigital number を列挙して
11-pandigital number であるものに対して
10-super-pandigital number であるものを求めて
最初の 10 個足す

12-pandigital number の列挙は配列

a[12] = { 1, 0, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 };

に対して next_permutation を回せば簡単にできる．11! * 11 = 439084800 パターンある．

n-pandigital number を求める関数は

bool is_pandigital(ll x, ll base = 10LL) {
    int bits = 0;
    while (x) {
        bits |= (1 << (x % base));
        x /= base;
    }
    return (bits == (1 << base) - 1 ? true : false);
}

とビットを用いて速くした．

b 進数の各桁の数字 d に対して bits の下位 d ビット目をオンにする．
pandigital であれば全ての桁に対して操作を行った後の bits は 2^b - 1 となっているはず．

11-pandigital を別で調べているのはパターンが約 4 億と多く，候補をある程度絞るため．
12-pandigital かつ 11-pandigital である数はだいたい 1,000,000 個くらいなので，あとは適当にやっても問題ない．

typedef long long ll;

bool is_pandigital(ll x, ll base = 10LL) {
    int bits = 0;
    while (x) {
        bits |= (1 << (x % base));
        x /= base;
    }
    return (bits == (1 << base) - 1 ? true : false);
}

bool is_super_pandigital(ll x, ll base = 10LL) {
    bool res = true;
    for (ll b = 2; b <= base; b++) res &= is_pandigital(x, b);
    return res;
}

int main() {

    clock_t start, end;
    start = clock();

    // 12-pandigital number : 11! * 11 = 439084800 pattern
    ll a[] = { 1,0,2,3,4,5,6,7,8,9,10,11 };
    vector<ll> vec;
    do {
        ll b = 1, x = 0;
        for (int i = 11; i >= 0; i--) {
            x += a[i] * b;
            b *= 12;
        }
        // 11-pandigital number
        if (is_pandigital(x, 11)) {
            // 10-super-pandigital number
            if(is_super_pandigital(x, 10)) vec.push_back(x);
        }
    } while (next_permutation(a, a + 12));

    cout << accumulate(vec.begin(), vec.begin() + 10, 0LL) << endl;

    end = clock();
    printf("%d msec.\n", end - start);

    return 0;
}

約 90 sec かかった．多分もっといい方法がある．

絶滅

どうでもいい

Project Euler - Problem 571

Super Pandigital Numbers