読者です 読者をやめる 読者になる 読者になる

Project Euler 43

Problem 43

using System;
using System.Collections.Generic;
using System.Linq;

class PE043 {
    static long Calc(int p, int[] digits, bool[] used) {
        int[] ds = { 0, 0, 2, 3, 5, 7, 11, 13, 17 };
        long ret = 0;

        int x = 100 * digits[p-3] + 10 * digits[p-2] + digits[p-1];
        if (x % ds[p-1] != 0) return 0;

        if (p == digits.Length) {
            long head = Enumerable.Range(0, 10).Where(e => !used[e]).First();
            long ans = digits.Aggregate(head, (a, b) => 10*a+b);
            Console.WriteLine(ans);
            return ans;
        }

        for (int i = 0; i < 10; i++) {
            if (used[i]) continue;

            used[i] = true;
            digits[p] = i;
            ret += Calc(p+1, digits, used);
            used[i] = false;
        }
        return ret;
    }
    
    static void Main() {
        long ans = 0;

        for (int i = 0; i < 10; i++) {
            for (int j = 0; j < 10; j++) {
                if (i == j) continue;
                for (int k = 0; k < 10; k++) {
                    if (i == k || j == k) continue;

                    bool[] used = new bool[10];
                    int[] digits = new int[9]; // 最上位は含まない
                    digits[0] = i;
                    digits[1] = j;
                    digits[2] = k;
                    used[i] = used[j] = used[k] = true;
                    ans += Calc(3, digits, used);
                    used[i] = used[j] = used[k] = false;
                }
            }
        }
        Console.WriteLine(ans);
    }
}