結果
| 問題 |
No.2795 Perfect Number
|
| コンテスト | |
| ユーザー |
 Slephy
|
| 提出日時 | 2024-06-30 12:28:05 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 3 ms / 2,000 ms |
| コード長 | 8,402 bytes |
| コンパイル時間 | 8,322 ms |
| コンパイル使用メモリ | 447,524 KB |
| 最終ジャッジ日時 | 2025-02-22 01:37:21 |
|
ジャッジサーバーID （参考情報） |
judge2 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 35 |
ソースコード
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int INF = (int)1e9 + 1001010;
const ll llINF = (long long)4e18 + 22000020;
const string endn = "\n";
template <class T> inline auto vector2(size_t i, size_t j, const T &init = T()) {return vector(i, vector<T>(j, init));}
const string ELEM_SEPARATION = " ", VEC_SEPARATION = endn;
template<class T> istream& operator >>(istream &i, vector<T> &A) {for(auto &I : A) {i >> I;} return i;}
template<class T> ostream& operator <<(ostream &o, const vector<T> &A) {int i=A.size(); for(const auto &I : A){o << I << (--i ? ELEM_SEPARATION : "");} return o;}
template<class T> ostream& operator <<(ostream &o, const vector<vector<T>> &A) {int i=A.size(); for(const auto &I : A){o << I << (--i ? VEC_SEPARATION : "");} return o;}
template<class T> vector<T>& operator ++(vector<T> &A, int n) {for(auto &I : A) {I++;} return A;}
template<class T> vector<T>& operator --(vector<T> &A, int n) {for(auto &I : A) {I--;} return A;}
template<class T, class U> bool chmax(T &a, const U &b) {return ((a < b) ? (a = b, true) : false);}
template<class T, class U> bool chmin(T &a, const U &b) {return ((a > b) ? (a = b, true) : false);}
ll floor(ll a, ll b){if (b < 0) a = -a, b = -b; if(a >= 0) return a / b; else return (a + 1) / b - 1;}
ll ceil(ll a, ll b){if (b < 0) a = -a, b = -b; if(a > 0) return (a - 1) / b + 1; else return a / b;}
ll bit(unsigned long long val, unsigned long long digit){return (val >> digit) & 1;}
#ifdef DEBUG
#include <debug_slephy.cpp>
#else
#define debug(...)
#endif
// ================================== ここまでテンプレ ==================================
//------------------------------//
// Prime Functions
//------------------------------//
// montgomery modint (MOD < 2^62, MOD is odd)
struct MontgomeryModInt64 {
using mint = MontgomeryModInt64;
using u64 = uint64_t;
using u128 = __uint128_t;
// static menber
static u64 MOD;
static u64 INV_MOD; // INV_MOD * MOD ≡ 1 (mod 2^64)
static u64 T128; // 2^128 (mod MOD)
// inner value
u64 val;
// constructor
MontgomeryModInt64() : val(0) { }
MontgomeryModInt64(long long v) : val(reduce((u128(v) + MOD) * T128)) { }
u64 get() const {
u64 res = reduce(val);
return res >= MOD ? res - MOD : res;
}
// mod getter and setter
static u64 get_mod() { return MOD; }
static void set_mod(u64 mod) {
assert(mod < (1LL << 62));
assert((mod & 1));
MOD = mod;
T128 = -u128(mod) % mod;
INV_MOD = get_inv_mod();
}
static u64 get_inv_mod() {
u64 res = MOD;
for (int i = 0; i < 5; ++i) res *= 2 - MOD * res;
return res;
}
static u64 reduce(const u128 &v) {
return (v + u128(u64(v) * u64(-INV_MOD)) * MOD) >> 64;
}
// arithmetic operators
mint operator + () const { return mint(*this); }
mint operator - () const { return mint() - mint(*this); }
mint operator + (const mint &r) const { return mint(*this) += r; }
mint operator - (const mint &r) const { return mint(*this) -= r; }
mint operator * (const mint &r) const { return mint(*this) *= r; }
mint operator / (const mint &r) const { return mint(*this) /= r; }
mint& operator += (const mint &r) {
if ((val += r.val) >= 2 * MOD) val -= 2 * MOD;
return *this;
}
mint& operator -= (const mint &r) {
if ((val += 2 * MOD - r.val) >= 2 * MOD) val -= 2 * MOD;
return *this;
}
mint& operator *= (const mint &r) {
val = reduce(u128(val) * r.val);
return *this;
}
mint& operator /= (const mint &r) {
*this *= r.inv();
return *this;
}
mint inv() const { return pow(MOD - 2); }
mint pow(u128 n) const {
mint res(1), mul(*this);
while (n > 0) {
if (n & 1) res *= mul;
mul *= mul;
n >>= 1;
}
return res;
}
// other operators
bool operator == (const mint &r) const {
return (val >= MOD ? val - MOD : val) == (r.val >= MOD ? r.val - MOD : r.val);
}
bool operator != (const mint &r) const {
return (val >= MOD ? val - MOD : val) != (r.val >= MOD ? r.val - MOD : r.val);
}
mint& operator ++ () {
++val;
if (val >= MOD) val -= MOD;
return *this;
}
mint& operator -- () {
if (val == 0) val += MOD;
--val;
return *this;
}
mint operator ++ (int) {
mint res = *this;
++*this;
return res;
}
mint operator -- (int) {
mint res = *this;
--*this;
return res;
}
friend istream& operator >> (istream &is, mint &x) {
long long t;
is >> t;
x = mint(t);
return is;
}
friend ostream& operator << (ostream &os, const mint &x) {
return os << x.get();
}
friend mint pow(const mint &r, long long n) {
return r.pow(n);
}
friend mint inv(const mint &r) {
return r.inv();
}
};
typename MontgomeryModInt64::u64
MontgomeryModInt64::MOD, MontgomeryModInt64::INV_MOD, MontgomeryModInt64::T128;
// Miller-Rabin
bool MillerRabin(long long N, vector<long long> A) {
using mint = MontgomeryModInt64;
mint::set_mod(N);
long long s = 0, d = N - 1;
while (d % 2 == 0) {
++s;
d >>= 1;
}
for (auto a : A) {
if (N <= a) return true;
mint x = mint(a).pow(d);
if (x != 1) {
long long t;
for (t = 0; t < s; ++t) {
if (x == N - 1) break;
x *= x;
}
if (t == s) return false;
}
}
return true;
}
bool is_prime(long long N) {
if (N <= 1) return false;
else if (N == 2) return true;
else if (N % 2 == 0) return false;
else if (N < 4759123141LL)
return MillerRabin(N, {2, 7, 61});
else
return MillerRabin(N, {2, 325, 9375, 28178, 450775, 9780504, 1795265022});
}
// Pollard's Rho
unsigned int xor_shift_rng() {
static unsigned int tx = 123456789, ty=362436069, tz=521288629, tw=88675123;
unsigned int tt = (tx^(tx<<11));
tx = ty, ty = tz, tz = tw;
return ( tw=(tw^(tw>>19))^(tt^(tt>>8)) );
}
long long pollard(long long N) {
if (N % 2 == 0) return 2;
if (is_prime(N)) return N;
using mint = MontgomeryModInt64;
mint::set_mod(N);
long long step = 0;
while (true) {
mint r = xor_shift_rng(); // random r
auto f = [&](mint x) -> mint { return x * x + r; };
mint x = ++step, y = f(x);
while (true) {
long long p = gcd((y - x).get(), N);
if (p == 0 || p == N) break;
if (p != 1) return p;
x = f(x);
y = f(f(y));
}
}
}
vector<long long> prime_factorize(long long N) {
if (N == 1) return {};
long long p = pollard(N);
if (p == N) return {p};
vector<long long> left = prime_factorize(p);
vector<long long> right = prime_factorize(N / p);
left.insert(left.end(), right.begin(), right.end());
sort(left.begin(), left.end());
return left;
}
#include <boost/multiprecision/cpp_int.hpp>
using i128 = boost::multiprecision::int128_t;
using i256 = boost::multiprecision::int256_t;
using i512 = boost::multiprecision::int512_t;
using i1024 = boost::multiprecision::int1024_t;
using iINF = boost::multiprecision::cpp_int;
#include <boost/multiprecision/cpp_dec_float.hpp>
using d30 = boost::multiprecision::number<boost::multiprecision::cpp_dec_float<30>>;
using d50 = boost::multiprecision::cpp_dec_float_50;
using d100 = boost::multiprecision::cpp_dec_float_100;
i128 powll(i128 base, i128 exponent){
i128 ret = 1;
while(exponent > 0){
if(exponent & 1) ret = ret * base;
base = base * base;
exponent >>= 1;
}
return ret;
}
int main(int argc, char *argv[]){
ios::sync_with_stdio(false);
cin.tie(nullptr);
ll n; cin >> n;
vector<ll> factors = prime_factorize(n);
map<i128, i128> fac_pow;
for(int i = 0; i < factors.size(); i++){
fac_pow[factors[i]]++;
}
i128 ans = 1;
for(auto [r, n] : fac_pow){
i128 sum = (powll(r, n+1) - 1) / (r - 1);
debug(r, n, sum);
ans *= sum;
}
if(ans == 2*n) cout << "Yes" << endl;
else cout << "No" << endl;
return 0;
}