結果

問題 No.1626 三角形の構築
コンテスト
ユーザー Kude
提出日時 2021-07-23 23:19:57
言語 C++17
(gcc 13.3.0 + boost 1.89.0)
結果
WA  
実行時間 -
コード長 2,354 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 4,068 ms
コンパイル使用メモリ 271,284 KB
最終ジャッジ日時 2025-01-23 08:56:47
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 1
other AC * 5 WA * 18 TLE * 3
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include<bits/stdc++.h>
#include<atcoder/all>
using namespace std;
using namespace atcoder;
#define rep(i,n)for (int i = 0; i < int(n); ++i)
#define rrep(i,n)for (int i = int(n)-1; i >= 0; --i)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
template<class T> void chmax(T& a, const T& b) {a = max(a, b);}
template<class T> void chmin(T& a, const T& b) {a = min(a, b);}
using ll = long long;
using P = pair<int,int>;
using VI = vector<int>;
using VVI = vector<VI>;
using VL = vector<ll>;
using VVL = vector<VL>;

map<long long, int> factorize(long long x) {
    map<long long, int> ret;
    for(long long p = 2; p * p <= x; p++) {
        int cnt = 0;
        while(x % p == 0) x /= p, cnt++;
        if (cnt) ret[p] = cnt;
    }
    if (x > 1) ret[x] = 1;
    return ret;
}

VL divisors(vector<pair<ll, int>> fs) {
    VL ret{1};
    for(auto [p, cnt]: fs) {
        ll now = 1;
        const int sz = ret.size();
        for(int i = 1; i <= cnt; i++) {
            now *= p;
            rep(j, sz) ret.push_back(ret[j] * now);
        }
    }
    sort(all(ret));
    return ret;
}

void solve() {
    ll s, t;
    cin >> s >> t;
    const ll Z = s * s * 16 / t;
    auto fs = factorize(s);
    for(auto& [k, v]: fs) v *= 2;
    fs[2] += 4;
    auto ft = factorize(t);
    for(auto [k, v]: ft) fs[k] -= v;
    vector<pair<ll, int>> factors;
    for(auto [k, v]: fs) {
        if (v < 0) {
            cout << 0 << '\n';
            return;
        }
        if (v) factors.emplace_back(k, v);
    }
    auto divs = divisors(factors);
    int sz = divs.size();
    vector<tuple<int, int, int>> ans;
    rep(i, sz) rep(j, sz) {
        ll ta = divs[i], tb = divs[j];
        if (ta >= t || tb >= t) continue;
        __int128_t x = 1;
        x *= ta;
        x *= tb;
        if (Z % x != 0) continue;
        ll tc = Z / x;
        if (tc >= t) continue;
        ll a = t - ta, b = t - tb, c = t - tc;
        if (a % 2 || b % 2 || c % 2) continue;
        a /= 2, b /= 2, c /= 2;
        if (abs(a - b) < c && c < abs(a + b)) {
            ans.emplace_back(a, b, c);
        }
    }
    cout << ans.size() << '\n';
    for(auto [a, b, c]: ans) {
        cout << a << ' ' << b << ' ' << c << '\n';
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int tt;
    cin >> tt;
    while(tt--) solve();
}
0