Project Euler で紹介されている問題43を解いてみました。ある条件を満たすパンデジタル数の総和を求めます。ライブラリで順列を使える C++ を利用して解きました。
Project Euler 問題43（割り切れる部分文字列）
数字 1406357289 は、0 から 9 までの各数字が1回ずつ現われるため、0 から 9 までのパンデジタル数です。その部分文字列は、以下の興味深い性質を持っています。
d1 を 1 桁目、d2 を 2 桁目、… とします。
- d2d3d4 = 406 は 2 で割り切れます。
- d3d4d5 = 063 は 3 で割り切れます。
- d4d5d6 = 635 は 5 で割り切れます。
- d5d6d7 = 357 は 7 で割り切れます。
- d6d7d8 = 572 は 11 で割り切れます。
- d7d8d9 = 728 は 13 で割り切れます。
- d8d9d10 = 289 は 17 で割り切れます。
同じ性質を持つ、0 から 9 までのパンデジタル数の合計を求めよ。
解答例
パンデジタル数については、問題32、問題38、問題41でも取り扱いました。今回のパンデジタル数は、0 を含みます。
C では標準ライブラリで順列のサポートがありません。標準ライブラリで順列のサポートがある C++ を使って解きます。順列を生成して、問題の条件を満たすか確認していくだけです。
確認する関数 is_satisfied を分けてプログラムしました。is_satisfied では、条件を満足しない場合が多い 17 から確認しています。また 5、2 の倍数の判定は末尾の数字だけから判断しています（20行目と27行目）。
解答を格納する変数 answer は、32ビットに収まらないため、long long 型としました。最終的に、C++ のプログラムは以下となります。
#include <iostream>
#include <algorithm>
using namespace std;
bool is_satisfied(int n[10])
{
if ((n[7] * 100 + n[8] * 10 + n[9])% 17 != 0) {
return false;
}
if ((n[6] * 100 + n[7] * 10 + n[8])% 13 != 0) {
return false;
}
if ((n[5] * 100 + n[6] * 10 + n[7])% 11 != 0) {
return false;
}
if ((n[4] * 100 + n[5] * 10 + n[6])% 7 != 0) {
return false;
}
if (n[5] % 5 != 0) {
/* n[3] * 100 + n[4] * 10 + n[5])% 5 == 0 */
return false;
}
if ((n[2] * 100 + n[3] * 10 + n[4])% 3 != 0) {
return false;
}
if (n[3] % 2 != 0) {
/* n[1] * 100 + n[2] * 10 + n[3])% 2 == 0 */
return false;
}
return true;
}
int main(void)
{
int n[10] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
long long int answer = 0;
do {
if (is_satisfied(n)) {
long long int num = 0;
for (int i = 0; i < 10; ++i) {
num = num * 10 + n[i];
}
printf("%lld\n", num);
answer += num;
}
} while (next_permutation(n, n + 10));
printf("Problem043: %lld\n", answer);
return 0;
}条件を満たす6個のパンデジタル数が見つかり、このプログラムの出力が正解と判定されました。
最後に
条件を満たすパンデジタル数を丁寧に求めていく問題でした。
引き続き、Project Euler の問題を紹介していきます。
