問題34
145 は興味深い数字である. なぜなら, となるからである.
http://projecteuler.net/index.php?section=problems&id=34
各桁の数字の階乗の合計が自身と等しくなる数の合計を求めよ.
ただし, と は含まない.
「問題30と同じじゃん. プログラムがそのまま使えるぞ! 上限は…(計算中)…7桁までの数字でいいんだな.」と意気込んでやってみた結果は……まず失敗……. 145 以外の答えが見付からない……orz
「なんでー?」と思いながら, アルゴリズムの改良なんかをやってみたりしてたら, ふと気が付いた. そうだ じゃん, で計算してたら合うわけないよ.
最終学歴を抹消した方が良いでしょうか? いやー, めっちゃ凹んだ. やっぱ四六時中数学に触れてないと, そういう細かいところが鈍るのね…….
#include <stdio.h> #include <stdlib.h> const long long RADIX = 10; const long long UPPER_BOUND = 10000000LL; const int fact[10] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880}; long long solveVer00(); long long solveVer01(); long long sumOfFactorials(long long); int curious(long long); int main() { fprintf(stdout, "Solution: %lld\n", solveVer01()); return EXIT_SUCCESS; } long long solveVer00() { long long number; long long result; for (number = 3, result = 0; number < UPPER_BOUND; number++) { // fprintf(stdout, "%lld, %lld\n", number, sumOfFactorials(number)); if (curious(number)) { fprintf(stdout, "%lld\n", number); result += number; } } return result; } long long solveVer01() { long long number; long long result; int lastDigit; long long upperPart; long long sum; for (upperPart = 0, result = 0; upperPart < UPPER_BOUND / RADIX; upperPart++) { for (lastDigit = 0; lastDigit < RADIX; lastDigit++) { number = upperPart * RADIX + lastDigit; sum = sumOfFactorials(number); if (sum < 3) { continue; } if (sum > number) { break; } else if (sum == number) { fprintf(stdout, "%lld\n", number); result += number; } } } return result; } int curious(long long number) { int digit; long long sum; long long copy; sum = 0; copy = number; while (copy) { digit = copy % RADIX; copy /= RADIX; sum += fact[digit]; if (number < sum) { return 0; } } return number == sum; } long long sumOfFactorials(long long number) { int digit; long long result; result = 0; while (number) { digit = number % RADIX; number /= RADIX; result += fact[digit]; } return result; }