結果
問題 | No.1626 三角形の構築 |
ユーザー |
![]() |
提出日時 | 2021-07-23 22:44:18 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 348 ms / 2,000 ms |
コード長 | 2,291 bytes |
コンパイル時間 | 3,173 ms |
コンパイル使用メモリ | 196,672 KB |
最終ジャッジ日時 | 2025-01-23 08:29:00 |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 26 |
ソースコード
#include <cstdio> #include <cstring> #include <iostream> #include <string> #include <cmath> #include <bitset> #include <vector> #include <map> #include <set> #include <queue> #include <deque> #include <algorithm> #include <complex> #include <unordered_map> #include <unordered_set> #include <random> #include <cassert> #include <fstream> #include <utility> #include <functional> #include <time.h> #include <stack> #include <array> #include <list> #include <atcoder/all> #define popcount __builtin_popcount using namespace std; using namespace atcoder; typedef long long ll; typedef pair<ll, int> P; int main() { int T; cin>>T; while(T--){ ll s, t; cin>>s>>t; if(16*s*s%t!=0){ cout<<0<<endl; continue; } map<ll, int> mp; ll s1=s, t1=t; for(ll p=2; p*p<=s1; p++){ if(s1%p==0){ while(s1%p==0){ s1/=p; mp[p]+=2; } } } if(s1>1) mp[s1]+=2; mp[2]+=4; for(ll p=2; p*p<=t1; p++){ if(t1%p==0){ while(t1%p==0){ t1/=p; mp[p]--; } } } if(t1>1) mp[t1]--; vector<P> f; for(auto p:mp) f.push_back(p); vector<ll> v; auto dfs=[&](auto dfs, ll x, int k)->void{ if(k==f.size()){ if(t>x && (t-x)%2==0){ v.push_back(x); } return; } ll p=f[k].first, x1=x; for(int i=0; i<=f[k].second; i++){ if(x1<t) dfs(dfs, x1, k+1); x1*=p; } }; dfs(dfs, 1, 0); ll u=16*s*s/t; vector<pair<pair<ll, ll>, ll>> ans; for(auto x:v){ for(auto y:v){ if(u/x%y!=0 || (t-u/x/y)%2!=0) continue; ll a=(t-x)/2, b=(t-y)/2, c=(t-u/x/y)/2; if(c>0 && a+b+c==t && a<=b && b<=c && c<=1000000000){ ans.push_back({{a, b}, c}); } } } cout<<ans.size()<<endl; for(auto q:ans) cout<<q.first.first<<" "<<q.first.second<<" "<<q.second<<endl; } return 0; }