結果
| 問題 | No.888 約数の総和 |
| コンテスト | |
| ユーザー |
 n_bitand_n_per_3
|
| 提出日時 | 2026-06-02 01:26:01 |
| 言語 | C++23 (gcc 15.2.0 + boost 1.89.0) |
| 結果 |
AC
|
| 実行時間 | 2 ms / 2,000 ms |
| コード長 | 8,202 bytes |
| 記録 | |
| コンパイル時間 | 3,012 ms |
| コンパイル使用メモリ | 241,176 KB |
| 実行使用メモリ | 6,400 KB |
| 最終ジャッジ日時 | 2026-06-02 01:26:06 |
| 合計ジャッジ時間 | 3,213 ms |
|
ジャッジサーバーID （参考情報） |
judge2_0 / judge3_0 |
| 純コード判定待ち |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 30 |
ソースコード
#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <set>
#include <unordered_map>
#include <map>
#include <unordered_set>
#include <queue>
#include <algorithm>
#include <iomanip>
#include <functional>
#include <cassert>
#include <bit>
#include <array>
#include <random>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using uint = unsigned int;
#define LL __int128
#define ld long double
#define INF 2251799813685248
#define rep(i, n) for (ll i = 0; i < (n); ++i)
#define reps(i, l, r) for(ll i = (l); i < (r); ++i)
#define foreach(c, A) for(auto c:(A))
#define vall(A) (A).begin(),(A).end()
#define vrall(A) (A).rbegin(),(A).rend()
#define slice(A, l, r) next((A).begin(), (l)), next((A).begin(), (r))
#define vin(A) for (ll iiii = 0, szszszsz = (A).size(); iiii < szszszsz; iiii++){cin >> (A)[iiii];}
#define vout(A) for (ll iiii = 0, szszszsz = (A).size(); iiii < szszszsz; iiii++){cout << (A)[iiii] << " \n"[iiii == szszszsz-1];}
#define vin2d(A) for (ll iiii = 0; iiii < (A).size(); iiii++){for (ll jjjj = 0; jjjj < (A)[iiii].size(); jjjj++){cin >> (A)[iiii][jjjj];}}
#define vout2d(A) for (ll iiii = 0; iiii < (A).size(); iiii++){for (ll jjjj = 0; jjjj < (A)[iiii].size(); jjjj++){cout << (A)[iiii][jjjj] << " \n"[jjjj==(A)[iiii].size()-1];}}
#define encode(i,j) (((i))<<32)+(j)
#define decode(v,w) ((w) ? (v)%4294967296 : (v)>>32)
#define vinc(A) for (auto &vvvv : (A)){vvvv++;}
#define vdec(A) for (auto &vvvv : (A)){vvvv--;}
#define graphin0(C, M) int aaaa,bbbb;for (int iiii = 0; iiii < (M); iiii++){cin >> aaaa >> bbbb; (C)[aaaa].push_back(bbbb); (C)[bbbb].push_back(aaaa);}
#define graphin1(C, M) int aaaa,bbbb;for (int iiii = 0; iiii < (M); iiii++){cin >> aaaa >> bbbb; (C)[aaaa-1].push_back(bbbb-1); (C)[bbbb-1].push_back(aaaa-1);}
#define lsegtype(name) name::S, name::F
#define lsegarg(name) name::op, name::e,name::comp, name::mapping, name::id
vector<ll> pow2ll{1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,131072,262144,524288,1048576,2097152,4194304,8388608,16777216,33554432,67108864,134217728,268435456,536870912,1073741824,2147483648,4294967296,8589934592,17179869184,34359738368,68719476736,137438953472,274877906944,549755813888,1099511627776,2199023255552,4398046511104,8796093022208,17592186044416,35184372088832,70368744177664,140737488355328,281474976710656,562949953421312,1125899906842624,2251799813685248,4503599627370496,9007199254740992,18014398509481984,36028797018963968,72057594037927936,144115188075855872,288230376151711744,576460752303423488,1152921504606846976,2305843009213693952,4611686018427387904};
vector<ll> pow10ll{1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000,10000000000,100000000000,1000000000000,10000000000000,100000000000000,1000000000000000,10000000000000000,100000000000000000,1000000000000000000};
vector<ll> di{0,1,0,-1};
vector<ll> dj{1,0,-1,0};
template <typename T>
bool chmax(T &a, const T& b) { return a < b ? a = b, true : false; }
template <typename T>
bool chmin(T &a, const T& b) { return a > b ? a = b, true : false; }
unsigned int bit_length(ll n){ return n > 0 ? 64 - __builtin_clzll(n) : 0;}
template <typename T>
T sum(vector<T> A){
T res = 0;
for (size_t i=0;i<A.size();i++){
res += A[i];
}
return res;
}
ll powll(ll a, ll n, ll m){
if (n == 0){return 1;}
if (n == 1){return a % m;}
LL ans = 1;
LL p = a;
while(n > 0){
if ((n & 1) == 1){
ans *= p;
ans %= m;
}
n >>= 1;
p *= p;
p %= m;
}
return (ll)ans;
}
__int128_t powlarge(__int128_t a, __int128_t n){
if (n == 0){return 1;}
if (n == 1){return a;}
__int128_t ans = 1;
__int128_t p = a;
while(n > 0){
if ((n & 1) == 1){
ans *= p;
}
n >>= 1;
p *= p;
}
return ans;
}
// Injecting boilerplate.hpp <- _lib/sum_divsor.hpp
// Skipping already injected boilerplate.hpp
// Skipping already injected boilerplate.hpp
// Skipping already injected boilerplate.hpp
// Skipping already injected boilerplate.hpp
// Skipping already injected boilerplate.hpp
template <typename T>
inline constexpr bool always_false_v = false;
template <typename T>
inline int bit_length(T n) {
if constexpr (std::is_same_v<T, int>) {
return n > 0 ? 32 - __builtin_clz(n) : 0;
} else if constexpr (std::is_same_v<T, uint>) {
return n > 0 ? 32 - __builtin_clz(n) : 0;
} else if constexpr (std::is_same_v<T, ll>) {
return n > 0 ? 64 - __builtin_clzll(n) : 0;
} else if constexpr (std::is_same_v<T, ull>) {
return n > 0 ? 64 - __builtin_clzll(n) : 0;
} else {
static_assert(always_false_v<T>, "bit_length: unsupported type");
return 0;
}
}
template <typename T>
inline int bit_count(T n) {
if constexpr (std::is_same_v<T, int>) {
return __builtin_popcount(n);
} else if constexpr (std::is_same_v<T, uint>) {
return __builtin_popcount(n);
} else if constexpr (std::is_same_v<T, ll>) {
return __builtin_popcountll(n);
} else if constexpr (std::is_same_v<T, ull>) {
return __builtin_popcountll(n);
} else {
static_assert(always_false_v<T>, "bit_count: unsupported type");
return 0;
}
}
// Injecting bit.hpp <- _lib/MillerRabin.hpp
bool MillerRabin(ll N, vector<ll> arr) {
int s = bit_length((N - 1) & (-(N - 1))) - 1;
ll d = (N - 1) >> s;
for (auto a : arr) {
if (N <= a) {
return true;
}
ll x = powll(a, d, N);
int t;
if (x != 1) {
for (t = 0; t < s; ++t) {
if (x == N - 1) break;
x = __int128_t(x) * x % N;
}
if (t == s) return false;
}
}
return true;
}
// Injecting MillerRabin.hpp <- _lib/isprime.hpp
constexpr bool isprime(ll N) {
if (N <= 1) {
return false;
}
if (N == 2) {
return true;
}
if (N % 2 == 0) {
return false;
}
if (N < 4759123141LL) {
return MillerRabin(N, {2, 7, 61});
} else {
return MillerRabin(N, {2, 325, 9375, 28178, 450775, 9780504, 1795265022});
}
}
// Injecting isprime.hpp <- _lib/Pollards_rho.hpp
ll find_factor(ll n){ // n should be composite number.
if (n % 2 == 0){
return 2;
}
for(int c=1;;c++){
auto f = [&](ll x){ return (__int128_t(x) * x + c) % n; };
ll x = 2, y = 2, d = 1;
while (d == 1){
x = f(x);
y = f(f(y));
d = gcd(abs(x - y), n);
}
if (d != n){
return d;
}
}
}
void Pollards_rho_Enumerater(ll n, vector<ll>& res){
if (isprime(n)){
res.push_back(n);
} else {
ll g = find_factor(n);
Pollards_rho_Enumerater(g, res);
Pollards_rho_Enumerater(n/g, res);
}
}
vector<ll> Pollards_rho(ll n){
vector<ll> res;
Pollards_rho_Enumerater(n, res);
sort(vall(res));
return res;
}
// Injecting Pollards_rho.hpp <- _lib/factorize.hpp
vector<ll> factorize_primitive(ll n){
vector<ll> factors;
for (ll i = 2; i * i <= n; i++) {
while (n % i == 0) {
n /= i;
factors.push_back(i);
}
}
if (n > 1) {
factors.push_back(n);
}
return factors;
}
vector<ll> factorize(ll n){
if (n <= 1000000){
return factorize_primitive(n);
} else {
return Pollards_rho(n);
}
}
// Injecting factorize.hpp <- _lib/sum_divsor.hpp
// Skipping already injected boilerplate.hpp
template <typename T, typename COUNTER_TYPE = int>
unordered_map<T,COUNTER_TYPE> Counter(vector<T> arr){
unordered_map<T,COUNTER_TYPE> res;
for(auto& x: arr){
res[x] += 1;
}
return res;
}
// Injecting Counter.hpp <- _lib/sum_divsor.hpp
ll sum_divsor(ll n){
auto factors = factorize(n);
auto dict = Counter(factors);
ll ans = 1;
for (auto [p, e]:dict){
ans *= (ll)((powlarge(p,e+1)-1)/(p-1));
}
return ans;
}
ll sum_divsor(unordered_map<ll,int>& dict){
ll ans = 1;
for (auto [p, e]:dict){
ans *= (ll)((powlarge(p,e+1)-1)/(p-1));
}
return ans;
}
// Injecting _lib/sum_divsor.hpp <- a.cpp
int main(){
ll a;
cin >> a;
cout << sum_divsor(a) << endl;
}