結果

問題 No.888 約数の総和
ユーザー ecotteaecottea
提出日時 2021-10-20 16:25:11
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 17,322 bytes
コンパイル時間 4,022 ms
コンパイル使用メモリ 247,752 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-09-20 06:36:03
合計ジャッジ時間 4,934 ms
ジャッジサーバーID
(参考情報)
judge4 / judge3
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#ifndef HIDDEN_IN_VISUAL_STUDIO //
//
#define _CRT_SECURE_NO_WARNINGS
// 使
#include <bits/stdc++.h>
using namespace std;
//
using ll = long long; // -2^63 2^63 = 9 * 10^18int -2^31 2^31 = 2 * 10^9
using pii = pair<int, int>; using pll = pair<ll, ll>; using pil = pair<int, ll>; using pli = pair<ll, int>;
using vi = vector<int>; using vvi = vector<vi>; using vvvi = vector<vvi>;
using vl = vector<ll>; using vvl = vector<vl>; using vvvl = vector<vvl>;
using vb = vector<bool>; using vvb = vector<vb>; using vvvb = vector<vvb>;
using vc = vector<char>; using vvc = vector<vc>; using vvvc = vector<vvc>;
using vd = vector<double>; using vvd = vector<vd>; using vvvd = vector<vvd>;
template <class T> using priority_queue_rev = priority_queue<T, vector<T>, greater<T>>;
using Graph = vvi;
//
const double PI = 3.14159265359;
const double DEG = PI / 180.; // θ [deg] = θ * DEG [rad]
const vi dx4 = { 1, 0, -1, 0 }; // 4
const vi dy4 = { 0, 1, 0, -1 };
const vi dx8 = { 1, 1, 0, -1, -1, -1, 0, 1 }; // 8
const vi dy8 = { 0, 1, 1, 1, 0, -1, -1, -1 };
const ll INFL = (ll)2e18; const int INF = (int)1e9;
const double EPS = 1e-10; // 調
//
#define all(a) (a).begin(), (a).end()
#define sz(x) ((int)(x).size())
#define distance (int)distance
#define Yes(b) {cout << ((b) ? "Yes" : "No") << endl;}
#define rep(i, n) for(int i = 0, i##_len = int(n); i < i##_len; ++i) // 0 n-1
#define repi(i, s, t) for(int i = int(s), i##_end = int(t); i <= i##_end; ++i) // s t
#define repir(i, s, t) for(int i = int(s), i##_end = int(t); i >= i##_end; --i) // s t
#define repe(v, a) for(const auto& v : (a)) // a
#define repea(v, a) for(auto& v : (a)) // a
#define repb(set, d) for(int set = 0; set < (1 << int(d)); ++set) // d
#define repp(a) sort(all(a)); for(bool a##_perm = true; a##_perm; a##_perm = next_permutation(all(a))) // a
#define repit(it, a) for(auto it = (a).begin(); it != (a).end(); ++it) //
#define repitr(it, a) for(auto it = (a).rbegin(); it != (a).rend(); ++it) //
//
template <class T> inline ll pow(T n, int k) { ll v = 1; rep(i, k) v *= n; return v; }
template <class T> inline bool chmax(T& M, const T& x) { if (M < x) { M = x; return true; } return false; } // true
    
template <class T> inline bool chmin(T& m, const T& x) { if (m > x) { m = x; return true; } return false; } // true
    
// >>, <<
template <class T, class U> inline istream& operator>> (istream& is, pair<T, U>& p) { is >> p.first >> p.second; return is; }
template <class T, class U> inline ostream& operator<< (ostream& os, const pair<T, U>& p) { os << "(" << p.first << "," << p.second << ")"; return os
    ; }
template <class T, class U, class V> inline istream& operator>> (istream& is, tuple<T, U, V>& t) { is >> get<0>(t) >> get<1>(t) >> get<2>(t); return
    is; }
template <class T, class U, class V> inline ostream& operator<< (ostream& os, const tuple<T, U, V>& t) { os << "(" << get<0>(t) << "," << get<1>(t)
    << "," << get<2>(t) << ")"; return os; }
template <class T, class U, class V, class W> inline istream& operator>> (istream& is, tuple<T, U, V, W>& t) { is >> get<0>(t) >> get<1>(t) >> get<2
    >(t) >> get<3>(t); return is; }
template <class T, class U, class V, class W> inline ostream& operator<< (ostream& os, const tuple<T, U, V, W>& t) { os << "(" << get<0>(t) << "," <<
    get<1>(t) << "," << get<2>(t) << "," << get<3>(t) << ")"; return os; }
template <class T> inline istream& operator>> (istream& is, vector<T>& v) { repea(x, v) is >> x; return is; }
template <class T> inline ostream& operator<< (ostream& os, const vector<T>& v) { repe(x, v) os << x << " "; return os; }
template <class T> inline ostream& operator<< (ostream& os, const set<T>& s) { repe(x, s) os << x << " "; return os; }
template <class T> inline ostream& operator<< (ostream& os, const unordered_set<T>& s) { repe(x, s) os << x << " "; return os; }
template <class T, class U> inline ostream& operator<< (ostream& os, const map<T, U>& m) { repe(p, m) os << p << " "; return os; }
template <class T, class U> inline ostream& operator<< (ostream& os, const unordered_map<T, U>& m) { repe(p, m) os << p << " "; return os; }
template <class T> inline ostream& operator<< (ostream& os, stack<T> s) { while (!s.empty()) { os << s.top() << " "; s.pop(); } return os; }
template <class T> inline ostream& operator<< (ostream& os, queue<T> q) { while (!q.empty()) { os << q.front() << " "; q.pop(); } return os; }
template <class T> inline ostream& operator<< (ostream& os, deque<T> q) { while (!q.empty()) { os << q.front() << " "; q.pop_front(); } return os; }
template <class T> inline ostream& operator<< (ostream& os, priority_queue<T> q) { while (!q.empty()) { os << q.top() << " "; q.pop(); } return os; }
// Visual Studio
#ifdef _MSC_VER
#define popcount (int)__popcnt // 1
#define popcountll (int)__popcnt64
inline int lsb(unsigned int n) { unsigned long i; _BitScanForward(&i, n); return i; } // 0-indexed
inline int lsbll(unsigned long long n) { unsigned long i; _BitScanForward64(&i, n); return i; }
inline int msb(unsigned int n) { unsigned long i; _BitScanReverse(&i, n); return i; } // 0-indexed
inline int msbll(unsigned long long n) { unsigned long i; _BitScanReverse64(&i, n); return i; }
template <class T> T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }
#define dump(x) cout << "\033[1;36m" << (x) << "\033[0m" << endl;
#define dumps(x) cout << "\033[1;36m" << (x) << "\033[0m ";
#define dumpel(a) { int i = 0; cout << "\033[1;36m"; repe(x, a) {cout << i++ << ": " << x << endl;} cout << "\033[0m"; }
#define input_from_file(f) ifstream isTMP(f); cin.rdbuf(isTMP.rdbuf());
#define output_to_file(f) ofstream osTMP(f); cout.rdbuf(osTMP.rdbuf());
// gcc
#else
#define popcount (int)__builtin_popcount
#define popcountll (int)__builtin_popcountll
#define lsb __builtin_ctz
#define lsbll __builtin_ctzll
#define msb(n) (31 - __builtin_clz(n))
#define msbll(n) (63 - __builtin_clzll(n))
#define gcd __gcd
#define dump(x)
#define dumps(x)
#define dumpel(v)
#define input_from_file(f)
#define output_to_file(f)
#endif
#endif //
//-----------------AtCoder -----------------
#include <atcoder/all>
using namespace atcoder;
//using mint = modint1000000007;
using mint = modint998244353;
//using mint = modint; // mint::set_mod(m);
template <class S, S(*op)(S, S), S(*e)()>ostream& operator<<(ostream& os, segtree<S, op, e> seg) { int n = seg.max_right(0, [](S x) {return true; });
    rep(i, n) os << seg.get(i) << " "; return os; }
template <class S, S(*op)(S, S), S(*e)(), class F, S(*mp)(F, S), F(*cp)(F, F), F(*id)()>ostream& operator<<(ostream& os, lazy_segtree<S, op, e, F, mp
    , cp, id> seg) { int n = seg.max_right(0, [](S x) {return true; }); rep(i, n) os << seg.get(i) << " "; return os; }
istream& operator>> (istream& is, mint& x) { ll x_; is >> x_; x = x_; return is; }
ostream& operator<< (ostream& os, const mint& x) { os << x.val(); return os; }
using vm = vector<mint>; using vvm = vector<vm>; using vvvm = vector<vvm>;
//----------------------------------------------
// F_p 64 bit
/*
* F_p
*
* : p gcc
*/
//using a__int128 = ll; //
struct mll {
__int128 v;
static __int128 MOD;
//
mll() : v(0) {};
mll(const mll& a) = default;
mll(const int& a) : v(safe_mod(a)) {};
mll(const ll& a) : v(safe_mod(a)) {};
//
mll& operator=(const mll& a) { v = a.v; return *this; }
mll& operator=(const int& a) { v = safe_mod(a); return *this; }
mll& operator=(const ll& a) { v = safe_mod(a); return *this; }
//
friend istream& operator>> (istream& is, mll& x) { ll tmp; is >> tmp; x.v = safe_mod(tmp); return is; }
friend ostream& operator<< (ostream& os, const mll& x) { os << (ll)x.v; return os; }
// mod
template <class T>
static __int128 safe_mod(T a) { return ((a % MOD) + MOD) % MOD; }
//
bool operator==(const mll& b) const { return v == b.v; }
bool operator==(const int& b) const { return v == safe_mod(b); }
bool operator==(const ll& b) const { return v == safe_mod(b); }
friend bool operator==(const int& a, const mll& b) { return b == a; }
friend bool operator==(const ll& a, const mll& b) { return b == a; }
//
mll& operator+=(const mll& b) { v = safe_mod(v + b.v); return *this; }
mll& operator-=(const mll& b) { v = safe_mod(v - b.v); return *this; }
mll& operator*=(const mll& b) { v = safe_mod(v * b.v); return *this; }
mll& operator/=(const mll& b) { *this *= b.inv(); return *this; }
mll operator+(const mll& b) const { mll a = *this; return a += b; }
mll operator-(const mll& b) const { mll a = *this; return a -= b; }
mll operator*(const mll& b) const { mll a = *this; return a *= b; }
mll operator/(const mll& b) const { mll a = *this; return a /= b; }
mll operator-() const { mll a = *this; return a *= -1; }
// int
mll& operator+=(const int& b) { v = safe_mod(v + b); return *this; }
mll& operator-=(const int& b) { v = safe_mod(v - b); return *this; }
mll& operator*=(const int& b) { v = safe_mod(v * b); return *this; }
mll& operator/=(const int& b) { *this *= mll(b).inv(); return *this; }
mll operator+(const int& b) const { mll a = *this; return a += b; }
mll operator-(const int& b) const { mll a = *this; return a -= b; }
mll operator*(const int& b) const { mll a = *this; return a *= b; }
mll operator/(const int& b) const { mll a = *this; return a /= b; }
friend mll operator+(const int& a, const mll& b) { return b + a; }
friend mll operator-(const int& a, const mll& b) { return -(b - a); }
friend mll operator*(const int& a, const mll& b) { return b * a; }
friend mll operator/(const int& a, const mll& b) { return mll(a) * b.inv(); }
// ll
mll& operator+=(const ll& b) { v = safe_mod(v + b); return *this; }
mll& operator-=(const ll& b) { v = safe_mod(v - b); return *this; }
mll& operator*=(const ll& b) { v = safe_mod(v * b); return *this; }
mll& operator/=(const ll& b) { *this *= mll(b).inv(); return *this; }
mll operator+(const ll& b) const { mll a = *this; return a += b; }
mll operator-(const ll& b) const { mll a = *this; return a -= b; }
mll operator*(const ll& b) const { mll a = *this; return a *= b; }
mll operator/(const ll& b) const { mll a = *this; return a /= b; }
friend mll operator+(const ll& a, const mll& b) { return b + a; }
friend mll operator-(const ll& a, const mll& b) { return -(b - a); }
friend mll operator*(const ll& a, const mll& b) { return b * a; }
friend mll operator/(const ll& a, const mll& b) { return mll(a) * b.inv(); }
//
mll pow(ll d) const {
mll res(1), pow2 = *this;
while (d > 0) {
if (d & 1LL) res *= pow2;
pow2 *= pow2;
d /= 2;
}
return res;
}
//
mll inv() const { return pow(MOD - 2); }
//
static void set_mod(ll MOD_) { MOD = MOD_; }
static ll mod() { return (ll)MOD; }
//
ll val() const { return (ll)safe_mod(v); }
};
__int128 mll::MOD;
// -
/*
* n
*
* F_p 64 bit
*/
bool miller_rabin(ll n) {
// : https://nyaannyaan.github.io/library/prime/fast-factorize.hpp.html
//
// p a=[1..p)
// a^(p-1) = 1 (mod p)
//
// p - 1 = 2^s d d :
//
// a^d = 1 (mod p) or ∃r=[0..s), a^(2^r d) = -1 (mod p)
//
//
// a
// n a
assert(n > 0);
const vl as = { 2, 325, 9375, 28178, 450775, 9780504, 1795265022 };
if (n == 2 || n == 3 || n == 5 || n == 13 || n == 19 || n == 73 || n == 193
|| n == 407521 || n == 299210837) return true;
if (n == 1 || n % 2 == 0) return false;
mll::set_mod(n);
int s = 0; ll d = n - 1LL;
while (d % 2 == 0) {
s++;
d /= 2;
}
repe(a, as) {
mll powa = mll(a).pow(d);
if (powa == 1 || powa == -1) goto LOOP_END;
rep(r, s - 1) {
powa *= powa;
if (powa == 1) return false;
if (powa == -1) goto LOOP_END;
}
return false;
LOOP_END:;
}
return true;
}
//ρO(n^(1/4))
/*
* n 1
*
* : n
*
* F_p 64 bit
*/
ll pollard_rho(ll n) {
// : https://qiita.com/Kiri8128/items/eca965fe86ea5f4cbb98
//
// c f : Z/nZ → Z/nZ
// f(x) = x^2 + c
//
//
// x[0] = y[0] (= 2) Z/nZ
// x[i + 1] = f(x[i]), y[i + 1] = f(f(y[i]))
//
// gcd(x[i] - y[i], n) = g ∈ (1..n)
// f Z/gZg n
//
//
// x r = (2 ) 1/2
// gcd m = n^(1/8) gcd log
//
assert(n >= 4);
if (!(n & 1)) return 2;
int m = 1 << (msbll(n) / 8);
mll::set_mod(n); // n 使
const int c_max = 99; // c
repi(c, 1, c_max) {
auto f = [&](mll x) { return x * x + c; };
mll x, y = 2, y_bak;
ll g = 1;
int r = 1;
// g = 1
while (g == 1) {
// x, y r = 2^i
x = y;
rep(hoge, r) y = f(y);
// r = 2^i
for (int k = 0; k < r; k += m) {
// g = n
y_bak = y;
// m
mll mul = 1;
rep(i, min(m, r - k)) {
y = f(y);
// gcd
// x
//
mul *= x - y;
}
g = gcd(mul.val(), n);
// g != 1
if (g != 1) goto LOOP_END;
}
r *= 2;
}
LOOP_END:;
// g = n
if (g == n) {
// x, y_bak
g = 1;
while (g == 1) {
y_bak = f(y_bak);
g = gcd((x - y_bak).val(), n);
}
}
// g < n g n
if (g < n) return g;
// g = n
// f c
}
// c
return n;
}
//ρO(n^(1/4))
/*
* n pps
*
* pps[p] = d : n p d
*
* - ρ
*/
void factor_integer_fast(ll n, map<ll, int>& pps) {
assert(n > 0);
pps.clear();
if (n == 1) return;
queue<ll> divs;
divs.push(n);
while (!divs.empty()) {
ll d = divs.front();
divs.pop();
if (miller_rabin(d)) {
pps[d]++;
}
else {
ll d1 = pollard_rho(d);
ll d2 = d / d1;
divs.push(d1);
divs.push(d2);
}
}
}
//O(n^(1/4))
/*
* n divs
*
* ρ
*/
void divisors(ll n, vl& divs) {
assert(n > 0);
map<ll, int> pps;
factor_integer_fast(n, pps);
divs = vl({ 1 });
repe(pp, pps) {
ll p; int d;
tie(p, d) = pp;
vl powp(d);
powp[0] = p;
rep(i, d - 1) powp[i + 1] = powp[i] * p;
int m = sz(divs);
repir(j, m - 1, 0) {
rep(i, d) {
divs.push_back(divs[j] * powp[i]);
}
}
}
sort(all(divs));
}
int main() {
cout << fixed << setprecision(15);
// input_from_file("input.txt");
// output_to_file("output.txt");
ll n;
cin >> n;
vl divs;
divisors(n, divs);
ll res = accumulate(all(divs), 0LL);
cout << res << endl;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0