結果
問題 |
No.2125 Inverse Sum
|
ユーザー |
![]() |
提出日時 | 2022-11-18 23:03:53 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 79 ms / 2,000 ms |
コード長 | 1,560 bytes |
コンパイル時間 | 2,508 ms |
コンパイル使用メモリ | 211,004 KB |
最終ジャッジ日時 | 2025-02-08 22:20:15 |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 30 |
ソースコード
#include <bits/stdc++.h> using namespace std; unordered_map<long long, int> factorize(long long x) { unordered_map<long long, int> mp; for( long long i = 2LL; i*i <= x; i++ ) { while( x%i == 0LL ) { mp[i]++; x /= i; } } if( x != 1LL ) mp[x]++; return mp; } int main() { // int N; // P*N*M=Q*(N+M) // P * N * M - Q * N - Q * M = 0 // ( P * M - Q ) * N - Q * M = 0 // ( P * M - Q ) * N + ( P * M - Q ) * ( - Q / P ) = Q * Q / P // ( P * M - Q ) * ( N - ( Q / P ) ) = Q * Q / P "( P * M - Q ) * ( P * N - Q ) = Q * Q"; long long P, Q; constexpr long long INF = 1LL<<61; cin >> P >> Q; vector<pair<long long, long long>> ans; unordered_map<long long, int> fact = factorize(Q); deque<long long> que1, que2; que1.emplace_back(1LL); for( auto& [p, t] : fact ) { long long pw = 1LL; for( int i = 0; i <= 2*t; i++, pw *= p ) { for( long long& crr : que1 ) { if( crr <= INF/pw ) que2.emplace_back(crr*pw); } } swap(que1, que2); que2.clear(); } for( long long& d : que1 ) { long long d2 = Q*Q/d; if( (d+Q)%P == 0LL && (d2+Q)%P == 0LL ) ans.emplace_back(make_pair((d+Q)/P, (d2+Q)/P)); if( (-d+Q)%P == 0LL && (-d2+Q)%P == 0LL && -d+Q > 0 && -d2+Q > 0 ) ans.emplace_back(make_pair((-d+Q)/P, (-d2+Q)/P)); } sort(ans.begin(), ans.end()); cout << ans.size() << endl; for( auto& [fi, se] : ans ) cout << fi << ' ' << se << endl; }