結果

問題 No.2125 Inverse Sum
コンテスト
ユーザー Fu_L
提出日時 2025-07-05 01:25:19
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 29 ms / 2,000 ms
コード長 1,658 bytes
コンパイル時間 4,125 ms
コンパイル使用メモリ 290,768 KB
実行使用メモリ 6,624 KB
最終ジャッジ日時 2025-07-05 01:25:25
合計ジャッジ時間 5,944 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<long long, long long>;
#define rep(i, a, b) for(long long i = (a); i < (b); ++i)
#define rrep(i, a, b) for(long long i = (a); i >= (b); --i)
constexpr long long inf = 4e18;
struct SetupIO {
    SetupIO() {
        ios::sync_with_stdio(0);
        cin.tie(0);
        cout << fixed << setprecision(30);
    }
} setup_io;
vector<pair<long long, int>> prime_factors(long long n) {
    assert(n >= 1);
    vector<pair<long long, int>> res;
    for(long long i = 2; i * i <= n; ++i) {
        if(n % i == 0) {
            res.emplace_back(i, 0);
            while(n % i == 0) {
                n /= i;
                ++res.back().second;
            }
        }
    }
    if(n >= 2) res.emplace_back(n, 1);
    return res;
}
int main(void) {
    ll p, q;
    cin >> p >> q;
    ll g = gcd(p, q);
    p /= g;
    q /= g;
    vector<pair<long long, int>> pf = prime_factors(q);
    rep(i, 0, ssize(pf)) {
        pf[i].second *= 2;
    }
    vector<ll> d;
    auto dfs = [&](auto& dfs, ll i, ll prod) -> void {
        if(i == ssize(pf)) {
            d.push_back(prod);
            return;
        }
        rep(j, 0, pf[i].second + 1) {
            dfs(dfs, i + 1, prod);
            prod *= pf[i].first;
        }
    };
    dfs(dfs, 0, 1);
    ranges::sort(d);
    set<P> ans;
    for(ll x : d) {
        ll y = q * q / x;
        x += q;
        y += q;
        if(x % p != 0 or y % p != 0) continue;
        ll n = x / p, m = y / p;
        ans.insert({n, m});
    }
    cout << ssize(ans) << '\n';
    for(auto [n, m] : ans) {
        cout << n << ' ' << m << '\n';
    }
}
0