結果
| 問題 |
No.1653 Squarefree
|
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 13:14:09 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 6,751 bytes |
| コンパイル時間 | 1,100 ms |
| コンパイル使用メモリ | 95,552 KB |
| 実行使用メモリ | 136,960 KB |
| 最終ジャッジ日時 | 2025-05-14 13:15:28 |
| 合計ジャッジ時間 | 7,655 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | -- * 3 |
| other | TLE * 1 -- * 37 |
ソースコード
#include <iostream>
#include <vector>
#include <cmath>
#include <limits> // Required for std::numeric_limits
#include <algorithm> // Required for std::max used in log calculation (optional optimization)
// Define unsigned long long for clarity and brevity
typedef unsigned long long ull;
// Function to generate primes up to a given limit using a basic Sieve of Eratosthenes.
// NOTE: This function is a placeholder. For the given constraints (R up to 10^18),
// sqrt(R) can be up to 10^9. A simple sieve up to 10^9 is too slow and uses too much memory.
// An efficient segmented sieve implementation is required for a solution that passes within time limits.
// The provided sieve is suitable only for smaller limits (e.g., up to ~10^7).
std::vector<ull> generate_primes(ull limit) {
if (limit < 2) return {}; // No primes less than 2
// Create a boolean vector to mark non-prime numbers. is_p[i] = true means i is potentially prime.
std::vector<bool> is_p(limit + 1, true);
is_p[0] = is_p[1] = false; // 0 and 1 are not prime
// Sieve of Eratosthenes
for (ull p = 2; p * p <= limit; ++p) {
if (is_p[p]) { // If p is prime
// Mark all multiples of p as not prime, starting from p*p
for (ull i = p * p; i <= limit; i += p)
is_p[i] = false;
}
}
// Collect all numbers marked as prime into a list
std::vector<ull> primes_list;
// Optimization: Reserve approximate space needed to reduce reallocations.
// Prime Number Theorem approximation: pi(x) ~ x/ln(x). Add a small buffer.
// Use std::max to avoid log(0) or log(1).
if (limit >= 2) {
primes_list.reserve(static_cast<size_t>(limit / log(std::max(2.0, (double)limit))) + 100);
}
for (ull p = 2; p <= limit; ++p) {
if (is_p[p]) {
primes_list.push_back(p);
}
}
return primes_list;
}
int main() {
// Use faster I/O operations
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
ull L, R; // Input range boundaries
std::cin >> L >> R;
// Calculate the total number of integers in the range [L, R]
ull N = R - L + 1;
// Create a boolean vector `is_marked` of size N.
// `is_marked[i] = true` indicates that the integer L + i is divisible by a perfect square > 1.
// Initially, assume all numbers are squarefree (not marked).
std::vector<bool> is_marked(N, false);
// Initialize the count of squarefree numbers to the total number of integers in the range.
ull count = N;
// Calculate floor(sqrt(R)) accurately using integer binary search to avoid floating point errors.
ull sqrt_R = 0;
ull low = 0, high = 1000000000ULL + 2; // Search space for sqrt(R). sqrt(10^18) = 10^9. Add buffer.
while(low <= high){
ull mid = low + (high - low) / 2; // Calculate midpoint carefully to avoid overflow
if (mid == 0) {
// If mid is 0, it can't be sqrt(R) unless R=0 (not possible here as L>=1).
// Continue search in the upper half [1, high].
low = mid + 1;
continue;
}
// Check for potential overflow before calculating mid * mid.
// If mid > ULLONG_MAX / mid, then mid * mid would overflow.
bool potential_overflow = (mid > std::numeric_limits<ull>::max() / mid);
if (potential_overflow || mid * mid > R) {
// If mid*mid overflows or is greater than R, mid is too large.
high = mid - 1;
} else {
// If mid*mid <= R, mid is a potential candidate for floor(sqrt(R)).
// Store mid and try larger values.
sqrt_R = mid;
low = mid + 1;
}
}
// Generate primes up to sqrt_R.
// WARNING: This line is the main performance bottleneck for large R.
// The included `generate_primes` function uses a basic sieve and will Time Limit Exceed
// if sqrt_R is large (e.g., 10^9). A proper solution requires an optimized segmented sieve.
std::vector<ull> primes_list;
if (sqrt_R > 0) {
// Call the prime generation function. Replace with optimized version if needed.
primes_list = generate_primes(sqrt_R);
}
// Iterate through the generated primes p. We only need primes p such that p*p <= R.
// Since we generated primes up to floor(sqrt(R)), this condition is implicitly satisfied.
for (ull p : primes_list) {
ull pp = p * p; // Calculate the square of the prime p.
// Calculate the first multiple of pp that is greater than or equal to L.
ull M_start;
ull rem = L % pp; // Find the remainder when L is divided by pp.
if (rem == 0) {
M_start = L; // If L is a multiple of pp, it's the first multiple >= L.
} else {
// Otherwise, the first multiple is L + (pp - rem). This finds the next multiple of pp after L.
// This calculation is safe from overflow as L <= 10^18, pp <= R <= 10^18.
// L + pp <= 2*10^18 which fits in unsigned long long.
M_start = L + (pp - rem);
}
// If the first multiple M_start is already greater than R, then no multiples of pp
// exist in the range [L, R]. Skip to the next prime.
if (M_start > R) {
continue;
}
// Iterate through all multiples M of pp within the range [L, R], starting from M_start.
for (ull M = M_start; M <= R; M += pp) {
// Calculate the index corresponding to M in the `is_marked` vector.
// M is guaranteed to be >= L, so idx >= 0.
ull idx = M - L;
// If the number M (at index idx) has not been marked yet,
// it means this is the first time we found a square factor for it.
// Mark it as not squarefree and decrement the count.
if (!is_marked[idx]) {
is_marked[idx] = true; // Mark L+idx as having a square factor > 1.
count--; // Decrement the count of squarefree numbers.
}
// Check to prevent potential overflow when calculating the next multiple M + pp.
// And break the loop if the next multiple would exceed R.
// This check `pp > R - M` is equivalent to `M + pp > R` but safer against overflow.
// Given R <= 10^18, M + pp will not overflow unsigned long long.
if (pp > R - M) {
break; // The next multiple M + pp would be > R.
}
}
}
// Output the final count of squarefree numbers in the range [L, R].
std::cout << count << std::endl;
return 0;
}