結果

問題 No.1626 三角形の構築
コンテスト
ユーザー tokusakurai
提出日時 2021-07-23 22:19:55
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 6 ms / 2,000 ms
コード長 4,062 bytes
コンパイル時間 2,317 ms
コンパイル使用メモリ 222,896 KB
最終ジャッジ日時 2025-01-23 08:05:57
ジャッジサーバーID
（参考情報） 		judge4 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < n; i++)
#define rep2(i, x, n) for(int i = x; i <= n; i++)
#define rep3(i, x, n) for(int i = x; i >= n; i--)
#define each(e, v) for(auto &e: v)
#define pb push_back
#define eb emplace_back
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define sz(x) (int)x.size()
using ll = long long;
using pii = pair<int, int>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
const int MOD = 1000000007;
//const int MOD = 998244353;
const int inf = (1<<30)-1;
const ll INF = (1LL<<60)-1;
template<typename T> bool chmax(T &x, const T &y) {return (x < y)? (x = y, true) : false;};
template<typename T> bool chmin(T &x, const T &y) {return (x > y)? (x = y, true) : false;};

struct io_setup{
    io_setup(){
        ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout << fixed << setprecision(15);
    }
} io_setup;

template<typename T>
vector<T> divisors(const T &n){
    vector<T> ret;
    for(T i = 1; i*i <= n; i++){
        if(n%i == 0){
            ret.push_back(i);
            if(i*i != n) ret.push_back(n/i);
        }
    }
    sort(begin(ret), end(ret));
    return ret;
}

template<typename T>
vector<pair<T, int>> prime_factor(T n){
    vector<pair<T, int>> ret;
    for(T i = 2; i*i <= n; i++){
        int cnt = 0;
        while(n%i == 0) cnt++, n /= i;
        if(cnt > 0) ret.emplace_back(i, cnt);
    }
    if(n > 1) ret.emplace_back(n, 1);
    return ret;
}

template<typename T>
bool is_prime(const T &n){
    if(n == 1) return false;
    for(T i = 2; i*i <= n; i++){
        if(n%i == 0) return false;
    }
    return true;
}

//1,2,...,nのうちkと互いに素である自然数の個数
template<typename T>
T coprime(T n, T k){
    vector<pair<T, int>> ps = prime_factor(k);
    int m = ps.size();
    T ret = 0;
    for(int i = 0; i < (1<<m); i++){
        T prd = 1;
        for(int j = 0; j < m; j++){
            if((i>>j)&1) prd *= ps[j].first;
        }
        ret += (__builtin_parity(i)? -1 : 1)*(n/prd);
    }
    return ret;
}

vector<bool> Eratosthenes(const int &n){
    vector<bool> ret(n+1, true);
    if(n >= 0) ret[0] = false;
    if(n >= 1) ret[1] = false;
    for(int i = 2; i*i <= n; i++){
        if(!ret[i]) continue;
        for(int j = i+i; j <= n; j += i) ret[j] = false;
    }
    return ret;
}

vector<int> Eratosthenes2(const int &n){
    vector<int> ret(n+1);
    iota(begin(ret), end(ret), 0);
    if(n >= 0) ret[0] = -1;
    if(n >= 1) ret[1] = -1;
    for(int i = 2; i*i <= n; i++){
        if(ret[i] < i) continue;
        for(int j = i+i; j <= n; j += i) ret[j] = min(ret[j], i);
    }
    return ret;
}

vector<pli> ps;
ll S, T;
set<tuple<ll, ll, ll>> ans;

void dfs(int i, ll P){
    if(i == sz(ps)){
        if(P >= T || (T-P)&1) return;
        ll A = (T-P)/2;
        ll K = S/P;
        ll D = sqrt(0.01+A*A-K);
        if(D*D == A*A-K){
            ll Q = A-D, R = A+D;
            if(Q < 0 || R < 0) return;
            if(Q >= T || (T-Q)&1) return;
            if(R >= T || (T-R)&1) return;
            ll B = (T-Q)/2;
            ll C = (T-R)/2;
            vector<ll> D = {A, B, C};
            sort(all(D));
            ans.emplace(D[0], D[1], D[2]);
        }
    }
    else{
        rep(j, ps[i].second+1){
            dfs(i+1, P);
            P *= ps[i].first;
        }
    }
}

int main(){
    int t; cin >> t;

    while(t--){
        ps.clear();
        ans.clear();
        S, T; cin >> S >> T;

        map<ll, int> mp;
        each(e, prime_factor(S)){
            mp[e.first] += e.second*2;
        }
        mp[2] += 4;
        each(e, prime_factor(T)){
            mp[e.first] -= e.second;
        }

        S *= S, S *= 16;

        if(S%T != 0){
            cout << "0\n";
            continue;
        }

        S /= T;

        each(e, mp) ps.eb(e);
        dfs(0, 1);

        cout << sz(ans) << '\n';
        each(e, ans){
            auto [A, B, C] = e;
            cout << A << ' ' << B << ' ' << C << '\n';
        }
    }
}
0