結果

問題 No.1626 三角形の構築
コンテスト
ユーザー Kude
提出日時 2021-07-24 02:04:06
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
(最新)
AC  
(最初)
実行時間 -
コード長 2,422 bytes
コンパイル時間 5,106 ms
コンパイル使用メモリ 270,120 KB
最終ジャッジ日時 2025-01-23 09:19:52
ジャッジサーバーID
（参考情報） 		judge4 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 25 WA * 1
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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) {
        ll ta = divs[i];
        if (ta >= t) break;
        rep(j, i + 1) {
            ll tb = divs[j];
            if (__int128_t(ta) * tb > Z) break;
            ll x = ta * tb;
            if (Z % x) continue;
            ll tc = Z / x;
            if (tc <= ta) break;
            if (tc >= t) continue;
            ll a = t - ta, b = t - tb, c = t - tc;
            if ((a | b | c) & 1) continue;
            a /= 2, b /= 2, c /= 2;
            if (a + b + c != t) continue;
            ans.emplace_back(c, a, b);
        }
    }
    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