#1083980 (C++17) No.1884 Sequence

• 問題: No.1884 Sequence
• ユーザー: qwewe
• 提出日時: 2025-05-14 13:12:58
• 言語: C++17 (gcc 13.3.0 + boost 1.87.0)
• 結果: AC
• 実行時間: 54 ms / 2,000 ms
• コード長: 7,634 bytes
• コンパイル時間: 1,258 ms
• コンパイル使用メモリ: 98,044 KB
• 実行使用メモリ: 7,936 KB
• 最終ジャッジ日時: 2025-05-14 13:13:48
• 合計ジャッジ時間: 5,385 ms
• ジャッジサーバーID （参考情報）: judge1 / judge4

ファイルパターン	結果
sample	AC * 3
other	AC * 40

ソースコード

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
#include <cmath>
#include <limits> // Required for std::numeric_limits

// Custom GCD function for long long using Euclidean algorithm
long long gcd(long long a, long long b) {
    // Ensure arguments are non-negative for standard GCD definition
    if (a < 0) a = -a;
    if (b < 0) b = -b;
    while (b) {
        a %= b;
        std::swap(a, b);
    }
    return a;
}

// Function to compute integer square root safely for large numbers using binary search
// Returns the largest integer x such that x*x <= n.
long long integer_sqrt(long long n) {
    if (n < 0) return 0; // Square root of negative number is not real
    if (n == 0) return 0;
    
    long long low = 1;
    // Set a safe upper bound. sqrt(10^15) is about 3.16e7. Max value of G is around 10^15.
    // Let's use a slightly larger bound, e.g., 2*10^9 covers sqrt(4*10^18).
    // Max value of long long is about 9*10^18, its sqrt is about 3*10^9.
    long long high = 3000000000LL; 
    
    // Optimization: if n itself is smaller than initial high, adjust high.
    if (high > n) high = n; 

    long long ans = 0;
    while(low <= high) {
        // Calculate mid carefully to avoid overflow
        long long mid = low + (high - low) / 2;
        
        // If mid is 0, something is wrong or n=0 which is handled. Avoid division by zero.
        if (mid == 0) break; 
        
        // Check for potential overflow before multiplication mid*mid
        long long max_ll = std::numeric_limits<long long>::max();
        // If mid > max_ll / mid, then mid*mid would overflow
        if (mid > max_ll / mid) { 
            // mid is definitely too large if multiplication overflows
            high = mid - 1; 
        } else if (mid * mid <= n) {
            // If mid*mid <= n, mid is a possible candidate for integer square root.
            // We want the largest such integer, so store it and try larger values.
            ans = mid; 
            low = mid + 1; 
        } else {
            // If mid*mid > n, mid is too large.
            high = mid - 1; 
        }
    }
    return ans; // ans holds the largest integer whose square is <= n
}


int main() {
    // Faster I/O
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    
    long long N_ll; // Read N as long long to potentially use in 64-bit calculations
    std::cin >> N_ll;
    // Convert N to int for vector size usage etc. Constraint N <= 2e5 fits in int.
    int N = static_cast<int>(N_ll); 

    std::vector<long long> A(N);
    std::vector<long long> P; // Store positive values from A
    P.reserve(N); // Reserve capacity for performance
    for (int i = 0; i < N; ++i) {
        std::cin >> A[i];
        if (A[i] > 0) {
            P.push_back(A[i]);
        }
    }
    
    int k = P.size(); // Number of positive values initially present
    
    // Case 1: If there are 0 or 1 positive values, we can always form an AP.
    // We can fill blanks and rearrange freely. For k=0, choose {1, 2, ..., N}. For k=1 with value p, choose {p, p+1, ..., p+N-1}.
    if (k <= 1) {
        std::cout << "Yes" << std::endl;
        return 0;
    }
    
    // Sort the positive values to identify distinct elements and check properties.
    std::sort(P.begin(), P.end());
    
    // Create a vector of distinct positive values.
    std::vector<long long> distinct_P = P;
    auto last = std::unique(distinct_P.begin(), distinct_P.end());
    distinct_P.erase(last, distinct_P.end());
    
    int k_prime = distinct_P.size(); // Number of distinct positive values.
    
    // Case 2: If all positive values are identical (k_prime = 1).
    // We can form an AP with common difference d=0. Example: {p, p, ..., p}.
    // Need to fill m blanks with p. Possible if p > 0. This is guaranteed.
    if (k_prime == 1) { 
        std::cout << "Yes" << std::endl;
        return 0;
    }
    
    // Case 3: If there are duplicates among positive values, but not all values are the same (k > k_prime > 1).
    // An AP with d != 0 must have distinct terms. An AP with d = 0 requires all terms to be equal.
    // Neither case works if S+ has duplicates but values are not all identical.
    if (k > k_prime) {
        std::cout << "No" << std::endl;
        return 0;
    }
    
    // Case 4: All positive values are distinct (k = k_prime >= 2).
    // Let the distinct sorted positive values be p_1, ..., p_k.
    long long p1 = distinct_P[0];
    long long pk = distinct_P[k_prime - 1];
    
    // Calculate the GCD of differences between consecutive distinct elements.
    // The common difference 'd' must be a divisor of this GCD.
    long long G = 0;
    // This check is logically redundant as we are in k_prime >= 2 case, but kept for clarity.
    if (k_prime >= 2) { 
       G = distinct_P[1] - distinct_P[0];
       for (int i = 2; i < k_prime; ++i) {
            G = gcd(G, distinct_P[i] - distinct_P[i-1]);
            // Optimization: If GCD becomes 1, it cannot get smaller. All further GCDs will be 1.
            if (G == 1) break; 
       }
    }

    // If G is 0 or negative, something unexpected happened (e.g., non-distinct values passed through checks).
    // Since p_i are distinct and sorted, differences are positive, so G must be positive.
    if (G <= 0) { 
         std::cout << "No" << std::endl; // Indicate failure or unexpected state
         return 0; 
    }

    // Calculate the difference between the largest and smallest positive values.
    long long diff_pk_p1 = pk - p1;
    // Calculate N-1, needed for the condition check. Use N_ll for 64-bit arithmetic safety.
    long long N_minus_1 = N_ll - 1; 
    
    // Basic check: N>=3 is given, so N-1 >= 2. N_minus_1 is positive.
    if (N_minus_1 <= 0) { 
         std::cout << "No" << std::endl; // Should not happen based on constraints
         return 0;
    }

    // Condition for possibility: there must exist a divisor 'd' of G such that pk - p1 <= d * (N - 1).
    // This is equivalent to d >= ceil( (pk - p1) / (N - 1) ).
    // Calculate the minimum required divisor value, MinD = ceil( (pk - p1) / (N - 1) )
    long long MinD;
    // Handle diff_pk_p1 = 0 case (means k_prime=1, already handled, but for safety)
    if (diff_pk_p1 == 0) { 
      MinD = 1; // Any positive divisor d works. Require d >= 1.
    } else {
       // Calculate ceiling using integer division: (X + Y - 1) / Y for positive X, Y
       MinD = (diff_pk_p1 + N_minus_1 - 1) / N_minus_1;
    }
     // Since common difference d must be positive, MinD must be at least 1.
     // If calculation gives 0 or less, set minimum requirement to 1.
     if (MinD <= 0) MinD = 1; 

    bool possible = false;
    // Compute integer square root of G to iterate divisors efficiently.
    long long sqrtG = integer_sqrt(G);

    // Iterate through divisors d of G up to sqrt(G).
    for (long long d = 1; d <= sqrtG; ++d) {
        if (G % d == 0) {
            // Check divisor d
            if (d >= MinD) {
                 possible = true;
                 break; // Found a suitable divisor, no need to check further.
            }
            
            // Check divisor G/d
            long long d2 = G / d;
            // Check if d2 satisfies the condition. No need to check if d2 == d separately.
            if (d2 >= MinD) {
                 possible = true;
                 break; // Found a suitable divisor
            }
        }
    }
    
    // Output the final result.
    if (possible) {
        std::cout << "Yes" << std::endl;
    } else {
        std::cout << "No" << std::endl;
    }
    
    return 0;
}