結果
| 問題 | No.3388 Sum of Function |
| コンテスト | |
| ユーザー |
|
| 提出日時 | 2026-11-18 01:01:20 |
| 言語 | C++23(gcc16) (gcc 16.2.0 + boost 1.92.0 + ACL) |
| 結果 |
AC
不安定
|
| 実行時間 | 1 ms / 2,000 ms |
| + 802µs | |
| コード長 | 14,581 bytes |
| 記録 | |
| コンパイル時間 | 2,865 ms |
| コンパイル使用メモリ | 369,792 KB |
| 実行使用メモリ | 9,884 KB |
| 最終ジャッジ日時 | 2026-11-18 01:01:25 |
| 合計ジャッジ時間 | 5,249 ms |
|
ジャッジサーバーID (参考情報) |
judge5_0 / judge4_0 |
(要ログイン)
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 23 |
ソースコード
// https://github.com/primesosu91/library
#include <bits/stdc++.h>
#include <cassert>
using namespace std;
using ll = long long;
using ld = long double;
using pll = pair<ll, ll>;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define rep1(i, n) for (ll i = 1; i <= (ll)(n); i++)
#define rrep(i, n) for (ll i = n - 1; i >= (ll)(0); i--)
#define rrep1(i, n) for (ll i = n; i >= (ll)(1); i--)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define el '\n'
#define sp ' '
#define YN(text) cout << (text ? "Yes" : "No") << el;
#define ANS cout << ans << el;
#define pqmax(...) priority_queue<__VA_ARGS__>
#define pqmin(...) priority_queue<__VA_ARGS__, vector<__VA_ARGS__>, greater<__VA_ARGS__>>
const ll inf = 4e18;
const ll MOD = 998244353;
const ll dx[4] = {1, 0, -1, 0};
const ll dy[4] = {0, 1, 0, -1};
const ll DX[8] = {1, 1, 0, -1, -1, -1, 0, 1};
const ll DY[8] = {0, 1, 1, 1, 0, -1, -1, -1};
template <class T> bool chmax(T& a, const T& b) { if (a < b) { a = b; return true; } return false; }
template <class T> bool chmin(T& a, const T& b) { if (a > b) { a = b; return true; } return false; }
struct Prime {
private:
using u64 = unsigned long long;
using u128 = __uint128_t;
int limit;
vector<int> spf;
vector<int> prime_list;
mutable u64 random_state;
// 64-bit 整数でオーバーフローしない剰余乗算・累乗
static u64 mul_mod(u64 a, u64 b, u64 mod) {
return (u64)((u128)a * b % mod);
}
static u64 pow_mod(u64 a, u64 b, u64 mod) {
u64 result = 1;
while (b > 0) {
if (b & 1) result = mul_mod(result, a, mod);
a = mul_mod(a, a, mod);
b >>= 1;
}
return result;
}
// 64-bit 整数に対する決定的 Miller-Rabin 判定
static bool miller_rabin(u64 n) {
if (n < 2) return false;
for (u64 p : {2ULL, 3ULL, 5ULL, 7ULL, 11ULL, 13ULL, 17ULL, 19ULL, 23ULL, 29ULL, 31ULL, 37ULL}) {
if (n % p == 0) return n == p;
}
u64 d = n - 1;
int s = __builtin_ctzll(d);
d >>= s;
for (u64 a : {2ULL, 325ULL, 9375ULL, 28178ULL, 450775ULL, 9780504ULL, 1795265022ULL}) {
a %= n;
if (a == 0) continue;
u64 x = pow_mod(a, d, n);
if (x == 1 || x == n - 1) continue;
bool composite = true;
for (int i = 1; i < s; i++) {
x = mul_mod(x, x, n);
if (x == n - 1) {
composite = false;
break;
}
}
if (composite) return false;
}
return true;
}
// Pollard's Rho で使用する擬似乱数 (SplitMix64)
u64 next_random() const {
u64 x = (random_state += 0x9e3779b97f4a7c15ULL);
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9ULL;
x = (x ^ (x >> 27)) * 0x94d049bb133111ebULL;
return x ^ (x >> 31);
}
// Brent 法による非自明な因数の探索 (n は合成数)
u64 pollard_rho(u64 n) const {
if (n % 2 == 0) return 2;
if (n % 3 == 0) return 3;
while (true) {
u64 y = next_random() % (n - 1) + 1;
u64 c = next_random() % (n - 1) + 1;
auto f = [&](u64 x) {
u64 z = mul_mod(x, x, n);
return z >= n - c ? z - (n - c) : z + c;
};
u64 g = 1, r = 1, q = 1, x = 0, ys = 0;
while (g == 1) {
x = y;
for (u64 i = 0; i < r; i++) y = f(y);
for (u64 k = 0; k < r && g == 1;) {
ys = y;
u64 len = min(128ULL, r - k);
for (u64 i = 0; i < len; i++) {
y = f(y);
u64 delta = x > y ? x - y : y - x;
q = mul_mod(q, delta, n);
}
g = gcd(q, n);
k += len;
}
r *= 2;
}
if (g == n) {
do {
ys = f(ys);
u64 delta = x > ys ? x - ys : ys - x;
g = gcd(delta, n);
} while (g == 1);
}
if (g != n) return g;
}
}
// 素因数を重複込みで求める
void factor_rec(u64 n, vector<u64>& factors) const {
if (n == 1) return;
if (n <= (u64)limit) {
while (n > 1) {
int p = spf[(int)n];
factors.push_back(p);
n /= p;
}
return;
}
if (miller_rabin(n)) {
factors.push_back(n);
return;
}
u64 d = pollard_rho(n);
factor_rec(d, factors);
factor_rec(n / d, factors);
}
public:
// 初期化: Prime(n) -> [0, n] の最小素因数と素数一覧を構築 (前提: n >= 0)
Prime(int n = 0) : limit(0), random_state((u64)chrono::steady_clock::now().time_since_epoch().count()) {
build(n);
}
// 再構築: build(n) -> [0, n] を前計算し直す (前提: n >= 0)
void build(int n) {
assert(n >= 0);
limit = n;
spf.assign((size_t)n + 1, 0);
prime_list.clear();
for (int i = 2; i <= n; i++) {
if (spf[i] == 0) {
spf[i] = i;
prime_list.push_back(i);
}
for (int p : prime_list) {
if (p > spf[i] || (long long)p * i > n) break;
spf[p * i] = p;
}
}
}
// 素数判定: is_prime(n) -> n が素数なら true (n <= 1 は false)
bool is_prime(long long n) const {
if (n < 2) return false;
if (n <= limit) return spf[(int)n] == n;
return miller_rabin((u64)n);
}
// 素数一覧: primes() -> 前計算範囲 [2, N] の素数への参照
const vector<int>& primes() const {
return prime_list;
}
// 素数列挙: enumerate(n) -> n 以下の全素数 (前提: 0 <= n <= N)
vector<int> enumerate(int n) const {
assert(0 <= n && n <= limit);
auto it = upper_bound(prime_list.begin(), prime_list.end(), n);
return vector<int>(prime_list.begin(), it);
}
// 区間素数列挙: enumerate(l, r) -> [l, r) の素数 (前提: 0 <= l <= r)
// r-1 <= N なら前計算済み素数列を使用、N >= 2 かつ N*N >= r-1 なら分割区間篩、それ以外は各候補を素数判定
// 広い区間では N >= max(2, ceil(sqrt(r-1))) を目安に前計算する(r >= 2)。
// 例: Prime prime(1000000); prime.enumerate(999999000000LL, 1000000000000LL);
// 前計算が不足する広い区間では Miller-Rabin 判定を繰り返すため、処理時間が大きくなる
vector<long long> enumerate(long long l, long long r) const {
assert(0 <= l && l <= r);
vector<long long> result;
l = max(l, 2LL);
if (l >= r) return result;
if (r - 1 <= limit) {
auto first = lower_bound(prime_list.begin(), prime_list.end(), l);
auto last = lower_bound(first, prime_list.end(), r);
result.insert(result.end(), first, last);
return result;
}
// √(r-1) 以下の素数が前計算済みなら、分割区間篩を使う
if (limit >= 2 && (long long)limit * limit >= r - 1) {
constexpr long long block_size = 1 << 20;
while (l < r) {
long long high = r - l > block_size ? l + block_size : r;
vector<char> is_prime_block((size_t)(high - l), true);
for (int p : prime_list) {
if ((long long)p * p >= high) break;
u128 first = max((u128)p * p, (((u128)l + p - 1) / p) * p);
if (first >= (u128)high) continue;
for (long long x = (long long)first; x < high;) {
is_prime_block[(size_t)(x - l)] = false;
if (high - x <= p) break;
x += p;
}
}
for (long long i = 0; i < high - l; i++) {
if (is_prime_block[(size_t)i]) result.push_back(l + i);
}
l = high;
}
return result;
}
// 範囲外では決定的 Miller-Rabin 法を用いる
if (l <= 2) {
result.push_back(2);
l = 3;
}
if (l % 2 == 0) l++;
while (l < r) {
if (is_prime(l)) result.push_back(l);
if (r - l <= 2) break;
l += 2;
}
return result;
}
// 素数個数: count(n) -> n 以下の素数の個数 π(n) (前提: 0 <= n <= N)
int count(int n) const {
assert(0 <= n && n <= limit);
return (int)(upper_bound(prime_list.begin(), prime_list.end(), n) - prime_list.begin());
}
// 素数総数: count() -> N 以下の素数の総数
int count() const {
return (int)prime_list.size();
}
// k 番目の素数: kth_prime(k) -> 0-index の素数 (前提: 0 <= k < count())
int kth_prime(int k) const {
assert(0 <= k && k < count());
return prime_list[k];
}
// 最小素因数: smallest_prime_factor(n) -> n の最小素因数 (前提: 2 <= n <= N)
int smallest_prime_factor(int n) const {
assert(2 <= n && n <= limit);
return spf[n];
}
// 素因数分解: factorize(n) -> {素因数, 指数} を昇順で返す (前提: n >= 1、n=1 では空)
// n <= N なら最小素因数から直接まとめ、時間 O(log n)、結果以外の追加領域 O(1)。
vector<pair<long long, int>> factorize(long long n) const {
assert(n >= 1);
vector<pair<long long, int>> result;
if (n <= limit) {
// 最小素因数を順に取り出すため、ソートは不要。
while (n > 1) {
int p = spf[(int)n], exponent = 0;
do {
n /= p;
exponent++;
} while (n > 1 && spf[(int)n] == p);
result.emplace_back(p, exponent);
}
return result;
}
vector<u64> factors;
factor_rec((u64)n, factors);
sort(factors.begin(), factors.end());
for (u64 p : factors) {
if (result.empty() || result.back().first != (long long)p) result.emplace_back((long long)p, 1);
else result.back().second++;
}
return result;
}
// 約数列挙: divisors(n) -> 正の約数を昇順に返す (前提: n >= 1)
vector<long long> divisors(long long n) const {
assert(n >= 1);
auto factors = factorize(n);
vector<long long> result = {1};
for (auto [p, e] : factors) {
size_t size = result.size();
long long power = 1;
for (int i = 0; i < e; i++) {
power *= p;
for (size_t j = 0; j < size; j++) result.push_back(result[j] * power);
}
}
sort(result.begin(), result.end());
return result;
}
// 約数個数: divisor_count(n) -> 正の約数の個数 (前提: n >= 1)
long long divisor_count(long long n) const {
assert(n >= 1);
long long result = 1;
for (auto [p, e] : factorize(n)) result *= e + 1;
return result;
}
// 約数総和: divisor_sum(n) -> 正の約数の総和 (前提: n >= 1、総和が long long に収まる)
long long divisor_sum(long long n) const {
assert(n >= 1);
u128 result = 1;
for (auto [p, e] : factorize(n)) {
u128 term = 1, power = 1;
for (int i = 0; i < e; i++) {
power *= (u64)p;
term += power;
}
result *= term;
}
assert(result <= (u128)LLONG_MAX);
return (long long)result;
}
// Euler の φ 関数: euler_phi(n) -> 1 <= k <= n かつ gcd(k,n)=1 の整数 k の個数 (前提: n >= 1)
long long euler_phi(long long n) const {
assert(n >= 1);
long long result = n;
for (auto [p, e] : factorize(n)) result = result / p * (p - 1);
return result;
}
// Möbius 関数: mobius(n) -> μ(n) ∈ {-1,0,1} (前提: n >= 1)
int mobius(long long n) const {
assert(n >= 1);
int result = 1;
for (auto [p, e] : factorize(n)) {
if (e >= 2) return 0;
result = -result;
}
return result;
}
// Euler の φ 関数の一括計算: euler_phi_table(n) -> φ(0)..φ(n) (前提: 0 <= n <= N、φ(0) は 0)
vector<int> euler_phi_table(int n) const {
assert(0 <= n && n <= limit);
vector<int> result(n + 1, 0);
if (n >= 1) result[1] = 1;
for (int i = 2; i <= n; i++) {
int p = spf[i], m = i / p;
result[i] = m % p == 0 ? result[m] * p : result[m] * (p - 1);
}
return result;
}
// Möbius 関数の一括計算: mobius_table(n) -> μ(0)..μ(n) (前提: 0 <= n <= N、μ(0) は 0)
vector<int> mobius_table(int n) const {
assert(0 <= n && n <= limit);
vector<int> result(n + 1, 0);
if (n >= 1) result[1] = 1;
for (int i = 2; i <= n; i++) {
int p = spf[i], m = i / p;
result[i] = m % p == 0 ? 0 : -result[m];
}
return result;
}
// 約数個数の一括計算: divisor_count_table(n) -> d(0)..d(n) (前提: 0 <= n <= N、d(0) は 0)
vector<int> divisor_count_table(int n) const {
assert(0 <= n && n <= limit);
vector<int> result(n + 1, 0), exponent(n + 1, 0);
if (n >= 1) result[1] = 1;
for (int i = 2; i <= n; i++) {
int p = spf[i], m = i / p;
if (m % p == 0) {
exponent[i] = exponent[m] + 1;
result[i] = result[m] / (exponent[m] + 1) * (exponent[i] + 1);
} else {
exponent[i] = 1;
result[i] = result[m] * 2;
}
}
return result;
}
};
void solve() {
ll a, b;
cin >> a >> b;
Prime P(100);
auto f = [&](ll x) { return x * x * x - x * x + x + 1; };
ll ans = 0;
for (int i=a; i<=b; i++) if (P.is_prime(i)) ans += f(i);
ANS
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
ll t = 1;
// cin >> t;
rep(i, t) solve();
}