結果

問題 No.1626 三角形の構築
ユーザー KudeKude
提出日時 2021-07-23 23:19:57
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 2,354 bytes
コンパイル時間 5,679 ms
コンパイル使用メモリ 272,312 KB
実行使用メモリ 10,624 KB
最終ジャッジ日時 2024-04-20 16:05:42
合計ジャッジ時間 13,466 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 WA -
testcase_02 AC 6 ms
5,376 KB
testcase_03 AC 5 ms
5,376 KB
testcase_04 AC 4 ms
5,376 KB
testcase_05 AC 4 ms
5,376 KB
testcase_06 AC 5 ms
5,376 KB
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
testcase_24 TLE -
testcase_25 -- -
testcase_26 -- -
権限があれば一括ダウンロードができます

ソースコード

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) 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