結果
問題 | No.1626 三角形の構築 |
ユーザー |
![]() |
提出日時 | 2021-07-23 23:05:44 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,820 ms / 2,000 ms |
コード長 | 2,471 bytes |
コンパイル時間 | 6,633 ms |
コンパイル使用メモリ | 171,484 KB |
最終ジャッジ日時 | 2025-01-23 08:45:57 |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
純コード判定しない問題か言語 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 26 |
ソースコード
#pragma GCC target("avx2") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #include <iostream> #include <algorithm> #include <iomanip> #include <vector> #include <queue> #include <set> #include <map> #include <tuple> #include <cmath> #include <numeric> #include <functional> #include <cassert> #define debug_value(x) cerr << "line" << __LINE__ << ":<" << __func__ << ">:" << #x << "=" << x << endl; #define debug(x) cerr << "line" << __LINE__ << ":<" << __func__ << ">:" << x << endl; template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; } template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; } using namespace std; typedef long long ll; vector<ll> facs(ll x){ vector<ll> ans; for(ll i = 1; i*i <= x; i++){ if(x%i == 0){ ans.push_back(i); if(i*i != x) ans.push_back(x/i); } } sort(ans.begin(), ans.end()); return ans; } ll sq_ll(ll x){ ll ans = sqrt(x)+0.1; if(ans*ans > x) ans--; return ans; } using T = tuple<ll, ll, ll>; void solve(){ ll S, t; cin >> S >> t; ll s = S*S*16; if(s%t != 0){ cout << 0 << endl; return; } ll x = s/t; vector<ll> v = facs(4*S); assert(v.size() <= 2000); vector<ll> st; for(int i = 0; i < v.size(); i++){ for(ll j = i; j < v.size(); j++){ ll p = v[i]*v[j]; if(x%p == 0) st.push_back(p); } } vector<T> ans; sort(st.begin(), st.end()); ll pre = -1; for(ll p: st){ if(pre == p) continue; pre = p; if(p >= t) continue; if(p%2 != t%2) continue; // q+r = l // q*r = m ll a = (t-p)/2; ll l = 2*a; ll m = x/p; ll D = l*l-4*m; if(D < 0) continue; ll sq = sq_ll(D); if(sq*sq != D) continue; if(l%2 != sq%2) continue; if(l <= sq) continue; ll q = (l-sq)/2; ll r = (l+sq)/2; if(q >= p){ if(t%2 != q%2) continue; if(t%2 != r%2) continue; ll b = (t-q)/2; ll c = (t-r)/2; ans.push_back(T(a, b, c)); } } cout << ans.size() << endl; for(auto [a, b, c]: ans) cout << a << ' ' << b << ' ' << c << endl; } int main(){ ios::sync_with_stdio(false); cin.tie(0); cout << setprecision(10) << fixed; int t; cin >> t; while(t--) solve(); }