結果
問題 |
No.3296 81-like number
|
ユーザー |
|
提出日時 | 2025-10-05 14:08:23 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 3 ms / 2,000 ms |
コード長 | 3,291 bytes |
コンパイル時間 | 3,158 ms |
コンパイル使用メモリ | 286,884 KB |
実行使用メモリ | 7,716 KB |
最終ジャッジ日時 | 2025-10-05 14:08:31 |
合計ジャッジ時間 | 3,704 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 15 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; using ull = unsigned long long; using ld = long double; using i128 = __int128_t; using uc = unsigned char; #define Max(X,Y) (((X) > (Y)) ? (X) : (Y)) #define Min(X,Y) (((X) < (Y)) ? (X) : (Y)) #define yes cout << "Yes" << endl; #define no cout << "No" << endl; #define YES yes return 0; #define NO no return 0; #define pc cout << count << endl; #define PC pc return 0; #define INF 0x1fffffff #define Eps LDBL_EPSILON #ifdef DEBUG #define dbg(X) cerr << X << endl #else #define dbg(...) #endif template <typename T> inline ostream& operator<<(ostream& os, const vector<T>& v) noexcept { if(!v.empty()) os << v[0]; for(size_t i = 1; i < v.size(); i++) os << " " << v[i]; return os; } template <typename T> void swap(T& a, T& b) { auto x = a; a = b; b = x; } template <typename T> size_t partition(vector<T>& list, size_t start, size_t end) { auto pivot = list[end-1]; auto hi = start; for(auto i = start; i < end - 1; i++) { if(list[i] <= pivot) { swap(list[hi], list[i]); hi++; } } swap(list[hi], list[end-1]); return hi; } template <typename T> void quicksort(vector<T>& list, size_t l, size_t r) { if(l < r) { auto pivot = partition(list, l, r); quicksort(list, l, pivot); quicksort(list, pivot + 1, r); } } struct string_set { map<size_t, vector<string_view>> registry = {}; bool contains(string_view s) { auto h = hash<string_view>()(s); return registry.contains(h) && find(registry[h].begin(), registry[h].end(), s) != registry[h].end(); } void add(string_view s) { auto h = hash<string_view>()(s); auto pos = find(registry[h].begin(), registry[h].end(), s); if(pos != registry[h].end()) return; registry[h].push_back(s); } void remove(string_view s) { auto h = hash<string_view>()(s); if(!registry.contains(h)) return; auto pos = find(registry[h].begin(), registry[h].end(), s); if(pos == registry[h].end()) return; registry[h].erase(pos); } }; template <typename T> struct BIT { ll n; vector<T> tree; BIT(ll size) : n(size + 1), tree(n, 0) {} void add(ll i, T x) { for (ll idx = i; idx < n; idx += (idx & -idx)) { tree[idx] += x; } } T sum(ll i) { T s(0); for (ll idx = i; idx > 0; idx -= (idx & -idx)) { s += tree[idx]; } return s; } }; int main() { cin.tie(nullptr); ll N; cin >> N; ll sqN = sqrtl(N); ld Nlg = log2l(N); vector<char> prime(sqN, 1); vector<ll> primes; primes.reserve(100000); prime[0] = 0; primes.push_back(2); for(ll i = 4; i <= sqN; i+=2) prime[i-1] = 0; for(ll i = 3; i <= sqN; i+=2) { if(!prime[i-1]) continue; for(ll j = i*i; j <= sqN; j+=i) prime[j-1] = 0; primes.push_back(i); } ll sum = 0; for(auto p : primes) { ll lim = Nlg/log2l(p); ll s = p; for(ll i = 0; i < lim; i++) s*=p; sum+=(s-1)/(p-1)-p-1; // dbg("added " << (s-1)/(p-1)-p-1 << " prime " << p << "lim " << lim); } cout << sum << endl; }