結果
問題 |
No.3301 Make Right Triangle
|
ユーザー |
|
提出日時 | 2025-10-05 16:32:54 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 83 ms / 2,000 ms |
コード長 | 4,447 bytes |
コンパイル時間 | 2,151 ms |
コンパイル使用メモリ | 210,192 KB |
実行使用メモリ | 7,720 KB |
最終ジャッジ日時 | 2025-10-05 16:33:01 |
合計ジャッジ時間 | 7,028 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 9 |
ソースコード
#include <vector> #ifndef ONLINE_JUDGE #define _GLIBCXX_DEBUG 1 #endif #include <bits/stdc++.h> #include <stdint.h> #define fn auto #define let auto #define each(x, a) for (auto &x : a) #define rep(i, a) for (int i = 0; i < (a); ++i) #define bisect_right(l, r, ret, do) \ u64 _l = (l), _r = (r); \ auto _do = (do); \ while (_l < _r) { \ u64 _m = (_l + _r) / 2; \ if (_do(_m)) { \ _l = _m + 1; \ } else { \ _r = _m; \ } \ } \ u64 ret = _l; #define bisect_left(l, r, ret, do) \ u64 _l = (l), _r = (r); \ auto _do = (do); \ while (_l < _r) { \ u64 _m = (_l + _r) / 2; \ if (_do(_m)) { \ _r = _m; \ } else { \ _l = _m + 1; \ } \ } \ u64 ret = _l; #define all(x) begin(x), end(x) #define rall(x) rbegin(x), rend(x) #define sz(x) ((int)(x).size()) using namespace std; using ll = long long; using i8 = int8_t; using i16 = int16_t; using i32 = int32_t; using i64 = int64_t; using u8 = uint8_t; using u16 = uint16_t; using u32 = uint32_t; using u64 = uint64_t; class Furui { public: Furui(u64 max) { internal = std::vector<u64>(max); primes = std::vector<u64>(); for (u64 i = 2; i < max; i += 1) { if (internal[i] != 0) continue; primes.push_back(i); for (u64 j = i; i < max; i += i) { internal[j] = i; } } } std::map<u64, u64> prime_divisors(u64 val) { let res = std::map<u64, u64>(); each(p, primes) { while (val % p == 0) { res[p] += 1; val /= p; } } return res; } std::vector<u64> divisors(std::map<u64, u64> &divs) { let keys = std::vector<u64>(); let num = u64{1}; let val = u64{1}; each(dkv, divs) { keys.push_back(dkv.first); num *= dkv.second; rep(_, dkv.second) { val *= dkv.first; } } let ret = std::vector<u64>(); ret.reserve(num); ret.push_back(num); divisors(val, divs, keys, 0, ret); return ret; } void divisors(u64 val, std::map<u64, u64> &divs, std::vector<u64> &keys, u64 n, std::vector<u64> &ret) { if (n == keys.size()) { return; } rep(i, divs[keys[n]]) { let v = val / pow(keys[n], i); divisors(v, divs, keys, n + 1, ret); if (i > 0) { ret.push_back(v); } } } private: std::vector<u64> internal; std::vector<u64> primes; }; fn main() -> int { cin.tie(0)->sync_with_stdio(0); cout << fixed << setprecision(15); let furui = Furui(u64{100000}); u64 in_t; cin >> in_t; rep(_, in_t) { u64 in_l; cin >> in_l; let divs = furui.prime_divisors(in_l); each(dk, divs) { divs[dk.first] *= 2; } let l2 = in_l * in_l; each(d, furui.divisors(divs)) { // cout << d << ";\n"; if (l2 % d != 0) { continue; } let dad = l2 / d; if ((dad - d) % 2 != 0) { continue; } if (dad < d) { continue; } let a = (dad - d) / 2; if (a == 0) { continue; } cout << in_l << " " << a << " " << a + d << "\n"; break; } } // your code here... }