結果
| 問題 |
No.1322 Totient Bound
|
| コンテスト | |
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 13:18:40 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 11,744 bytes |
| コンパイル時間 | 1,524 ms |
| コンパイル使用メモリ | 116,944 KB |
| 実行使用メモリ | 38,564 KB |
| 最終ジャッジ日時 | 2025-05-14 13:19:35 |
| 合計ジャッジ時間 | 9,728 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 15 TLE * 1 -- * 20 |
ソースコード
#include <iostream>
#include <vector>
#include <map>
#include <cmath>
#include <string>
#include <algorithm> // for std::reverse
// Use GCC/Clang built-in 128 bit integer type if available
#ifdef __GNUC__
typedef __uint128_t u128;
#else
// Fallback for other compilers, might not work for large N
typedef unsigned long long u128;
#warning "Using unsigned long long for 128-bit type. May overflow for large N."
#endif
typedef long long ll;
ll N_ll; // Input N (up to 10^10)
u128 N; // Use 128 bit integer type for N and calculations involving it
std::vector<int> primes; // Stores precomputed primes
// Bound for precomputed primes. sqrt(10^10) = 10^5.
// A slightly larger bound might provide safety or minor speedup.
const int PRIME_BOUND = 150000;
// Memoization tables for the recursive functions
// Key: pair of (index k / prime value p, current limit M)
// Value: computed count S(k, M) or S_large(p, M)
std::map<std::pair<int, u128>, u128> memo;
std::map<std::pair<ll, u128>, u128> memo_large;
// Primality test using trial division by precomputed primes
// Sufficient for numbers up to PRIME_BOUND^2. For N=10^10, need check up to sqrt(N)=10^5.
// PRIME_BOUND=150k ensures this check is sufficient for primes p s.t. p*p <= N+1
bool is_prime(ll n) {
if (n <= 1) return false;
if (n <= 3) return true;
if (n % 2 == 0 || n % 3 == 0) return false;
// Check divisibility by precomputed primes up to sqrt(n)
for (int p : primes) {
// Optimization: only check primes up to sqrt(n)
if ((ll)p * p > n) break;
if (n % p == 0) return false;
}
// If n survived trial division by primes up to sqrt(n), it's prime.
return true;
}
// Find the smallest prime strictly greater than p
ll get_next_prime(ll p) {
ll num = p + 1;
// Handle edge cases and start checking from an odd number > p
if (num <= 2) num = 2;
else if (num % 2 == 0) num++;
while(true) {
// Basic overflow check for signed long long
if (num < p) return -1;
if (is_prime(num)) return num;
// Check for potential overflow before adding 2
// Use LLONG_MAX from <limits> for robustness if needed
if (num <= 9223372036854775807LL - 2) {
num += 2;
} else {
return -1; // Overflow potential
}
}
}
// Forward declaration for the main recursive function S
u128 S(int k, u128 M);
/**
* Recursive function to count numbers x such that phi(x) <= M,
* where all prime factors of x are >= current_p.
* This function handles primes larger than PRIME_BOUND.
* It includes x=1 in its count.
*/
u128 S_large(ll current_p, u128 M) {
// Base case: If M is 0, no positive integer x satisfies phi(x) <= 0.
if (M == 0) return 0;
// Ensure current_p is at least 2. If it's <= 1, start with 2.
if (current_p <= 1) current_p = 2;
// Base case: If the smallest possible prime factor p leads to phi(p) = p-1 > M,
// then only x=1 can satisfy the condition.
// Check `current_p - 1 > M` is sufficient. `current_p > M + 1` implies this for M>=0.
if (current_p - 1 > M) {
return 1; // Only x=1 is possible.
}
// Memoization check
std::pair<ll, u128> state = {current_p, M};
if (memo_large.count(state)) {
return memo_large[state];
}
// Initialize count result. Includes x=1.
u128 res = 1;
ll p = current_p;
// Iterate through primes p >= current_p
while(true) {
// If p-1 > M, then this prime and subsequent larger primes cannot be factors.
if (p - 1 > M) {
break;
}
u128 p_val = p; // Use u128 for calculations involving p
u128 phi_pa; // Stores phi(p^a)
// Correct initialization for phi(p^1)
if (p == 2) phi_pa = 1;
else phi_pa = p_val - 1;
// Iterate through powers 'a' of the current prime p
for (int a = 1; ; ++a) {
// If phi(p^a) exceeds M, this power and higher powers are invalid.
if (phi_pa > M) break;
u128 next_M = M / phi_pa; // Calculate the remaining limit for phi(y)
ll next_p = get_next_prime(p); // Find the next prime after p
if (next_p == -1) break; // Error or overflow finding next prime
// Recursive call: count numbers y with prime factors >= next_p s.t. phi(y) <= next_M
res += S_large(next_p, next_M);
// Prepare for the next power: Calculate phi(p^(a+1))
u128 next_phi_pa;
bool overflow = false;
// Calculation depends on whether p=2 or p is an odd prime
if (p == 2) {
// phi(2^1)=1, phi(2^2)=2, phi(2^3)=4, ... phi(2^a)=2^{a-1}
if (a==1) next_phi_pa = 2; // For a=2, phi is 2
else { // For a > 1, phi(2^{a+1}) = phi(2^a) * 2
// Check overflow before multiplying by 2
if (phi_pa > ((u128)-1) / 2) { overflow = true; }
else next_phi_pa = phi_pa * 2;
}
} else {
// For odd prime p, phi(p^{a+1}) = p * phi(p^a)
// Check overflow before multiplying by p
if (phi_pa > 0 && p > ((u128)-1) / phi_pa) { overflow = true; }
else next_phi_pa = phi_pa * p;
}
if (overflow) break; // Stop if overflow detected
// Optimization: Check if next phi value will exceed M using division check.
// This helps prune the search slightly earlier than the loop condition `phi_pa > M`.
// Check `phi_pa > M / p` approximate `next_phi_pa > M` check.
if (p > 1 && phi_pa > 0 && phi_pa > M / p) {
// Break if current phi_pa times p exceeds M.
// Only valid if p > 1. Avoid division by zero. phi_pa > 0 ensures M/p is well-defined.
// This check handles the update logic for both p=2 and p>2 implicitly.
break;
}
phi_pa = next_phi_pa; // Update phi_pa for the next iteration (a+1)
// Safety break for excessively large exponents (e.g., > 64 for 128-bit numbers)
if (a > 128) break;
}
// Move to the next prime for the outer loop
ll next_p_iter = get_next_prime(p);
// Break if error finding next prime or if potential infinite loop (next_p <= p)
if (next_p_iter == -1 || next_p_iter <= p) break;
p = next_p_iter;
}
// Store result in memoization table and return
return memo_large[state] = res;
}
/**
* Main recursive function to count numbers x such that phi(x) <= M.
* It uses precomputed primes up to PRIME_BOUND and then transitions to S_large.
* k is the index in the `primes` vector for the smallest prime factor allowed.
* Includes x=1 in its count.
*/
u128 S(int k, u128 M) {
// Base case: If M is 0, count is 0.
if (M == 0) return 0;
// If index k is beyond the precomputed primes list, switch to S_large
if (k >= primes.size()) {
// Find the prime immediately following the last precomputed prime
ll start_p = (primes.empty() ? 2 : get_next_prime(primes.back()));
if (start_p == -1) return 1; // Error case, assume only x=1
// Call S_large starting from this prime
return S_large(start_p, M);
}
// Memoization check
std::pair<int, u128> state = {k, M};
if (memo.count(state)) {
return memo[state];
}
// Result count initialized. Includes x=1 by definition of the recursion.
u128 res = 1;
// Iterate through precomputed primes starting from index k
for (int i = k; i < primes.size(); ++i) {
ll p = primes[i];
// If p-1 > M, this prime and subsequent larger primes cannot be factors.
if (p - 1 > M) {
break;
}
u128 p_val = p;
u128 phi_pa; // Stores phi(p^a)
// Initialize phi(p^1)
if (p == 2) phi_pa = 1;
else phi_pa = p_val - 1;
// Iterate through powers 'a' of prime p
for (int a = 1; ; ++a) {
// Safety check for phi_pa becoming 0 unexpectedly (should not happen for p>=2)
if (phi_pa == 0 && a > 1) break;
// If phi(p^a) exceeds M, this power and higher ones are invalid.
if (phi_pa > M) break;
u128 next_M = M / phi_pa; // Remaining limit for phi(y)
// Recursive call: count numbers y with smallest prime factor index >= i+1
// such that phi(y) <= next_M.
res += S(i + 1, next_M);
// Prepare for next power: Calculate phi(p^(a+1))
u128 next_phi_pa;
bool overflow = false;
// Calculation depends on p
if (p == 2) {
if (a==1) next_phi_pa = 2; // phi(2^2) = 2
else {
if (phi_pa > ((u128)-1) / 2) { overflow = true; }
else next_phi_pa = phi_pa * 2;
}
} else {
if (phi_pa > 0 && p > ((u128)-1) / phi_pa) { overflow = true; }
else next_phi_pa = phi_pa * p;
}
if (overflow) break;
// Optimization using division check to prune early
if (p > 1 && phi_pa > 0 && phi_pa > M / p) {
break;
}
phi_pa = next_phi_pa; // Update phi_pa for next iteration (a+1)
// Safety break for large exponents
if (a > 128) break;
}
}
// After iterating through precomputed primes in the range [k, primes.size()-1],
// we need to add the contribution from numbers whose smallest prime factor
// is larger than primes.back(). This is handled by calling S(primes.size(), M).
// Note: This call will naturally transition to S_large.
// We must subtract 1 because S(primes.size(), M) also counts x=1, which is already included in the initial `res = 1`.
res += S(primes.size(), M) - 1;
// Store result in memo table and return
return memo[state] = res;
}
// Overload output stream operator for u128 type for printing results
std::ostream& operator<<(std::ostream& os, u128 val) {
if (val == 0) return os << "0";
std::string s = "";
u128 temp = val;
while (temp > 0) {
s += (char)('0' + temp % 10);
temp /= 10;
}
std::reverse(s.begin(), s.end());
// Handle case where string might be empty if val was 0 initially (already checked)
// If val > 0 but string is empty (should not happen), print 0?
if (s.empty()) return os << "0";
return os << s;
}
// Sieve of Eratosthenes to precompute primes up to a given limit
void sieve(int limit) {
primes.clear();
std::vector<bool> is_p(limit + 1, true);
is_p[0] = is_p[1] = false;
for (int p = 2; p * p <= limit; ++p) {
if (is_p[p]) {
for (int i = p * p; i <= limit; i += p)
is_p[i] = false;
}
}
for (int p = 2; p <= limit; ++p) {
if (is_p[p]) {
primes.push_back(p);
}
}
}
int main() {
// Faster I/O
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
// Read input N
std::cin >> N_ll;
N = N_ll; // Convert to 128-bit type
// Precompute primes using Sieve
sieve(PRIME_BOUND);
// Clear memoization tables before starting calculation
memo.clear();
memo_large.clear();
// Call the main recursive function starting with index 0 and limit N
std::cout << S(0, N) << std::endl;
return 0;
}