[yukicoder] No. 800 四平方定理
問題
方針
\( x^2 + y^2 \) の頻度をあらかじめ計算しておき、\( z^2 – w^2 + D \) が存在するかを調べます。また、定数倍高速化をすることで、\( N^3 \) のコードもギリギリ通りました。
コード
頻度計算
#include <bits/stdc++.h> using namespace std; typedef long long ll; int main() { int N, D; cin >> N >> D; int n = 2 * N * N + 1; int d[n]{}; for (int x = 1; x <= N; x++) { for (int y = 1; y <= N; y++) { d[x * x + y * y]++; } } int cnt = 0; for (int z = 1; z <= N; z++) { for (int w = 1; w <= N; w++) { int t = w * w - z * z + D; if (t >= 0 && t <= n - 1) { cnt += d[t]; } } } cout << cnt << "\n"; return 0; }
定数倍高速化
#include <bits/stdc++.h> using namespace std; typedef long long ll; int main() { ll N, D; cin >> N >> D; int cnt = 0; const int NN = N * N; int h, t, g, m; for (int x = 1; x <= N; x++) { g = x * x; for (int y = x ; y <= N; y++) { h = g + y * y - D; if (h > NN) break; if (h < 0) { m = max((int)sqrt(-h), y); } else { m = y; } for (int z = m; z <= N; z++) { t = h + z * z; if (t > NN) break; if (t <= 0) continue; int k = sqrt(t); if (k * k == t) { if (x != y && y != z) cnt += 6; else if (x == y && y != z) cnt += 3; else if (x != y && y == z) cnt += 3; else cnt += 1; } } } } cout << cnt << "\n"; return 0; }
ディスカッション
コメント一覧
まだ、コメントがありません