結果

問題 No.1626 三角形の構築
ユーザー KudeKude
提出日時 2021-07-24 02:04:06
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
(最新)
AC  
(最初)
実行時間 -
コード長 2,422 bytes
コンパイル時間 4,655 ms
コンパイル使用メモリ 283,344 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-10-12 11:56:18
合計ジャッジ時間 6,399 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 WA -
testcase_02 AC 6 ms
5,248 KB
testcase_03 AC 4 ms
5,248 KB
testcase_04 AC 3 ms
5,248 KB
testcase_05 AC 3 ms
5,248 KB
testcase_06 AC 4 ms
5,248 KB
testcase_07 AC 19 ms
5,248 KB
testcase_08 AC 27 ms
5,248 KB
testcase_09 AC 37 ms
5,248 KB
testcase_10 AC 22 ms
5,248 KB
testcase_11 AC 32 ms
5,248 KB
testcase_12 AC 11 ms
5,248 KB
testcase_13 AC 11 ms
5,248 KB
testcase_14 AC 22 ms
5,248 KB
testcase_15 AC 16 ms
5,248 KB
testcase_16 AC 24 ms
5,248 KB
testcase_17 AC 21 ms
5,248 KB
testcase_18 AC 15 ms
5,248 KB
testcase_19 AC 25 ms
5,248 KB
testcase_20 AC 27 ms
5,248 KB
testcase_21 AC 23 ms
5,248 KB
testcase_22 AC 37 ms
5,248 KB
testcase_23 AC 26 ms
5,248 KB
testcase_24 AC 121 ms
5,248 KB
testcase_25 AC 62 ms
5,248 KB
testcase_26 AC 8 ms
5,248 KB
権限があれば一括ダウンロードができます

ソースコード

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