結果
問題 |
No.2125 Inverse Sum
|
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
#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'; } }