結果
| 問題 |
No.2125 Inverse Sum
|
| コンテスト | |
| ユーザー |
 a16784542
|
| 提出日時 | 2022-11-18 23:43:20 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 276 ms / 2,000 ms |
| コード長 | 6,192 bytes |
| コンパイル時間 | 4,081 ms |
| コンパイル使用メモリ | 262,384 KB |
| 最終ジャッジ日時 | 2025-02-08 22:30:46 |
|
ジャッジサーバーID （参考情報） |
judge4 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 30 |
ソースコード
#if !__INCLUDE_LEVEL__
#include __FILE__
// a + b がオーバーフローするならtrueを返す
template <class T> bool overflow_if_add(T a, T b) {
return (std::numeric_limits<T>::max() - a) < b;
}
// a * b がオーバーフローするならtrueを返す
template <class T> bool overflow_if_mul(T a, T b) {
return (std::numeric_limits<T>::max() / a) < b;
}
//最大公約数
long long gcd(long long a, long long b){
if (a%b == 0){return(b);}
else{return(gcd(b, a%b));}
}
//最小公倍数
long long lcm(long long a, long long b){
ll g=gcd(a,b);
a/=g;
if(overflow_if_mul(a,b))return LONG_LONG_MAX;
return a * b;
}
//約数列挙
vector<long long> enum_divisors(long long N) {
vector<long long> res;
for (long long i = 1; i * i <= N; ++i) {
if (N % i == 0) {
res.push_back(i);
// 重複しないならば i の相方である N/i も push
if (N/i != i) res.push_back(N/i);
}
}
// 小さい順に並び替える
sort(res.begin(), res.end());
return res;
}
//素数列挙
std::vector<int> Eratosthenes( const int N )
{
std::vector<bool> is_prime( N + 1 );
for( int i = 0; i <= N; i++ )
{
is_prime[ i ] = true;
}
std::vector<int> res;
for( int i = 2; i <= N; i++ )
{
if( is_prime[ i ] )
{
for( int j = 2 * i; j <= N; j += i )
{
is_prime[ j ] = false;
}
res.emplace_back( i );
}
}
return res;
}
// 素因数分解
// 460 = 2^2 x 5 x 23 の場合
// 返り値は {{2, 2}, {5, 1}, {23, 1}}
vector<pair<long long, long long> > prime_factorize(long long N) {
// 答えを表す可変長配列
vector<pair<long long, long long> > res;
// √N まで試し割っていく
for (long long p = 2; p * p <= N; ++p) {
// N が p で割り切れないならばスキップ
if (N % p != 0) {
continue;
}
// N の素因数 p に対する指数を求める
int e = 0;
while (N % p == 0) {
// 指数を 1 増やす
++e;
// N を p で割る
N /= p;
}
// 答えに追加
res.emplace_back(p, e);
}
// 素数が最後に残ることがありうる
if (N != 1) {
res.emplace_back(N, 1);
}
return res;
}
struct Solver {
void solve() {
int p,q;cin>>p>>q;
int g=gcd(p,q);
p/=g;
q/=g;
auto eq=enum_divisors(q);
set<int> st;
rep(i,sz(eq))rep(j,sz(eq)){
st.insert(eq[i]*eq[j]);
}
V<int> ans1,ans2;
fore(i,st){
int l=i;
int r=q*q/i;
if((l+q)%p==0&&(r+q)%p==0){
int n=(l+q)/p;
int m=(r+q)/p;
ans1.emplace_back(n);
ans2.emplace_back(m);
}
}
cout<<sz(ans1)<<endl;
rep(i,sz(ans1)){
cout<<ans1[i]<<" "<<ans2[i]<<endl;
}
}};
signed main() {
int ts = 1;
// scanf("%lld",&ts);
rep(ti,ts) {
Solver solver;
solver.solve();
}
return 0;
}
#else
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace atcoder;
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
using namespace std;
#define int ll
using ll=long long;
using ld = long double;
using uint = unsigned;
using ull = unsigned long long;
using P=pair<int,int>;
using TP=tuple<int,int,int>;
template <class T> using V = vector<T>;
template <class T> using max_heap = priority_queue<T>;
template <class T> using min_heap = priority_queue<T, vector<T>, greater<>>;
#define FOR1(a) for (ll _ = 0; _ < ll(a); ++_)
#define FOR2(i, a) for (ll i = 0; i < ll(a); ++i)
#define FOR3(i, a, b) for (ll i = a; i < ll(b); ++i)
#define FOR4(i, a, b, c) for (ll i = a; i < ll(b); i += (c))
#define FOR1_R(a) for (ll i = (a)-1; i >= ll(0); --i)
#define FOR2_R(i, a) for (ll i = (a)-1; i >= ll(0); --i)
#define FOR3_R(i, a, b) for (ll i = (b)-1; i >= ll(a); --i)
#define FOR4_R(i, a, b, c) for (ll i = (b)-1; i >= ll(a); i -= (c))
#define overload4(a, b, c, d, e, ...) e
#define rep(...) overload4(__VA_ARGS__, FOR4, FOR3, FOR2, FOR1)(__VA_ARGS__)
#define rrep(...) overload4(__VA_ARGS__, FOR4_R, FOR3_R, FOR2_R, FOR1_R)(__VA_ARGS__)
#define fore(i,a) for(auto &i:a)
#define all(x) x.begin(),x.end()
#define sz(x) ((int)(x).size())
#define bp(x) (__builtin_popcountll((long long)(x)))
#define elif else if
#define mpa make_pair
#define bit(n) (1LL<<(n))
#define LB(c, x) distance((c).begin(), lower_bound(all(c), (x)))
#define UB(c, x) distance((c).begin(), upper_bound(all(c), (x)))
#define UNIQUE(x) sort(all(x)), x.erase(unique(all(x)), x.end())
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
template<typename T>istream& operator>>(istream&i,vector<T>&v){rep(j,sz(v))i>>v[j];return i;}
template<typename T>string join(const T&v,const string& d=""){stringstream s;rep(i,sz(v))(i?s<<d:s)<<v[i];return s.str();}
template<typename T>ostream& operator<<(ostream&o,const vector<T>&v){if(sz(v))o<<join(v," ");return o;}
template<typename T1,typename T2>istream& operator>>(istream&i,pair<T1,T2>&v){return i>>v.first>>v.second;}
template<typename T1,typename T2>ostream& operator<<(ostream&o,const pair<T1,T2>&v){return o<<v.first<<","<<v.second;}
template<typename T1,typename T2>bool mins(T1& x,const T2&y){if(x>y){x=y;return true;}else return false;}
template<typename T1,typename T2>bool maxs(T1& x,const T2&y){if(x<y){x=y;return true;}else return false;}
template<typename Tx, typename Ty>Tx dup(Tx x, Ty y){return (x+y-1)/y;}
template<typename T>ll suma(const vector<T>&a){ll res(0);for(auto&&x:a)res+=x;return res;}
template<typename T>ll suma(const V<V<T>>&a){ll res(0);for(auto&&x:a)res+=suma(x);return res;}
template<typename T>void uni(T& a){sort(rng(a));a.erase(unique(rng(a)),a.end());}
template<typename T>void prepend(vector<T>&a,const T&x){a.insert(a.begin(),x);}
const int INF = 1001001001;
const ll INFL = 3e18;
const int MAX = 2e6+5;
#endif