メインから。
時間を計るので、ちょいゴタゴタしてます。
1兆までなのでかなり時間がかかります。
いえ、力技コードなので処理時間は気にしてないですｗ
#include <iostream> #include <chrono> int main() { long long limit = 1000000000000; std::chrono::system_clock::time_point start; std::chrono::system_clock::time_point end; start = std::chrono::system_clock::now(); long long answer = solve(limit); end = std::chrono::system_clock::now(); long long elasped = std::chrono::duration_cast<std::chrono::microseconds>(end - start).count(); std::cout << "tims: " << elasped << " answer: " << answer << std::endl; }
次は solve。
static long long solve(long long limit) { long long sum = 0; for (long long n = 1; n * n < limit; n++) { if (isRuishinNumber(n)) { std::cout << n * n << std::endl; sum += n * n; } } return sum; }
n * n を使うのですが n も用意しておくのは sqrt() とか使って誤差が出るのを避けるためです。
最後は isRuishinNumber。
static bool isRuishinNumber(long long n) { long long nn = n * n; for (long long d = 2; d < n; d++) { long long q = (long long)floor((double)nn / (double)d); long long r = nn - d * q; if (r == 0) { continue; } if (d * d == q * r) { return true; } } return false; }
d は 2 から n (nn の平方根) 未満まで走査します。d=1 だと r が 0 に、d=n だと d と q が n になるため累進数の条件を満たしません。
さらに、d > n を計算しても d と q が入れ替わるだけなので計算は不要です。
r は「%」を使用せず、nn - d * q と四則演算のみで求めます。こちらのほうが処理が速いです。
また、r が 0 の場合は、d, q, r は幾何数列にならないので、さっさと次の処理を実行するようにします。
d, q, r の関係は、d は n (nn の平方根)より小さいため、かならず q > d となります。
また、nn を d で割った余りが r なので、かならず d > r となります。
つまり
q > d > r > 0
という関係になります。
また、q, d, r が幾何数列にならなければいけないので、
q : d = d : r
と書くことが出来ます。公比は特に求める必要はありません。
比例式は内項の積と外項の積が等しくなります。つまり、
d * d = q * r
これが q, d, r が幾何数列になる条件となります。
ここも除算を使用すると誤差が出てしまい、正しく判定できない可能性がありますから、
整数の乗算で判定するようにしています。これならば誤差の心配はいりません。
実行結果
9 10404 16900 97344 576081 6230016 7322436 12006225 36869184 37344321 70963776 196112016 256160025 1361388609 1380568336 8534988225 9729849600 12551169024 13855173264 16394241600 123383587600 142965659664 547674002500 tims: 3681753496 answer: 878454337159
答えは 878454337159 となります。
処理時間は 1 時間ぐらいかかっていますｗ
問題に正解すると Project Euler の公式ページのフォーラムが閲覧できるようになり、みんなが解いたプログラムを拝見することができ、プログラムのロジックの解説が書いてあったり、質問したり議論もできるようになっています。計算で瞬時（数ミリ秒）で解いてしまうすごいプログラムや、独特な面白いプログラムが掲載されていたりするので、すごく勉強になります。
