#1084013 (C++17) No.1653 Squarefree

• 問題: 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;
}