結果
問題 | No.152 貯金箱の消失 |
ユーザー |
|
提出日時 | 2020-09-25 05:36:24 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 296 ms / 5,000 ms |
コード長 | 993 bytes |
コンパイル時間 | 2,398 ms |
コンパイル使用メモリ | 198,972 KB |
最終ジャッジ日時 | 2025-01-14 20:27:47 |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 12 |
ソースコード
#include <bits/stdc++.h>using namespace std;#define REP(i,n) for(int i=0; i<(int)(n); i++)long long gcd(long long a, long long b) {if (b == 0)return a;return gcd(b, a%b);}vector<tuple<long long, long long, long long> >pythagorean_triple(long long ub) {vector<tuple<long long, long long, long long> >ret;for (long long m = 1; m * m <= ub; m++) {for (long long n = m + 1; m * m + n * n <= ub; n++) {if (m % 2 == n % 2) continue;if (gcd(m, n) > 1) continue;long long a = n * n - m * m;long long b = 2 * n * m;long long c = n * n + m * m;if (max({a, b, c}) <= ub) {ret.emplace_back(a, b, c);}}}return ret;}int main() {ios_base::sync_with_stdio(0);cin.tie(0);int L;cin >> L;long long ret = 0;for (auto &[a, b, c]: pythagorean_triple(L)) {if (4 * (a + b + c) <= L) {if (++ret == 1e6 + 3)ret = 0;}}cout << ret << endl;return 0;}