#1083833 (C++17) No.2244 Integer Complete

• 問題: No.2244 Integer Complete
• ユーザー: qwewe
• 提出日時: 2025-05-14 13:04:16
• 言語: C++17 (gcc 13.3.0 + boost 1.87.0)
• 結果: TLE
• 実行時間: -
• コード長: 7,160 bytes
• コンパイル時間: 930 ms
• コンパイル使用メモリ: 89,048 KB
• 実行使用メモリ: 6,272 KB
• 最終ジャッジ日時: 2025-05-14 13:06:15
• 合計ジャッジ時間: 5,595 ms
• ジャッジサーバーID （参考情報）: judge1 / judge4

ファイルパターン	結果
other	AC * 19 TLE * 1 -- * 40

ソースコード

#include <iostream>
#include <vector>
#include <cmath>
#include <numeric>

// Function to compute the integer square root of a non-negative long long n.
// Returns the largest integer x such that x*x <= n.
// Uses binary search for efficiency and to handle large numbers correctly.
long long isqrt(long long n) {
    // Base cases
    if (n < 0) return 0; // Or throw an error, but problem constraints imply non-negative values derived from positive integers.
    if (n == 0) return 0;
    
    // Set binary search range.
    // The maximum possible value of k could be large, potentially up to ~10^18.
    // sqrt(10^18) = 10^9. A safe upper bound is slightly larger.
    // 3*10^9 is sufficient since (3*10^9)^2 = 9*10^18 > max long long.
    long long low = 0, high = 3000000000LL; 
    long long ans = 0; // Stores the best candidate for floor(sqrt(n)) found so far.
    
    while(low <= high) {
        long long mid = low + (high - low) / 2; // Calculate midpoint safely to avoid overflow.

        // To check mid*mid <= n without overflow, use division: mid <= n / mid
        // Need to handle mid == 0 case separately to avoid division by zero.
        if (mid == 0) {
             // If mid is 0, 0*0 <= n is always true for non-negative n.
             // ans could be 0. Move low to 1 to continue search for positive roots.
             ans = mid; // Update ans potentially to 0
             low = 1; 
             continue;
        }
        
        // Check if mid is too large (mid*mid > n)
        if (mid > n / mid) { 
             high = mid - 1; // Mid is too large, search in the lower half.
        } else { 
             // mid*mid <= n. Mid is a potential candidate for the integer square root.
             ans = mid; // Update the best candidate found so far.
             low = mid + 1; // Try searching for a larger root in the upper half.
        }
    }
    return ans; // Return the largest integer x such that x*x <= n.
}


// Use boolean arrays to quickly check membership in A and B.
// The maximum value for A_i, B_j is 30000. Array size 30001 covers indices 1 to 30000.
const int MAX_VAL = 30001; 
bool hasA[MAX_VAL]; // hasA[x] is true if x is in deck A
bool hasB[MAX_VAL]; // hasB[x] is true if x is in deck B

// Function to check if integer k can be represented as a product xy
// where x is derived from some A_i and y from some B_j.
// x satisfies A_i^2 <= x < (A_i+1)^2 which means A_i = floor(sqrt(x)).
// y satisfies B_j^2 <= y < (B_j+1)^2 which means B_j = floor(sqrt(y)).
// We need to check if k = d1 * d2 such that floor(sqrt(d1)) is in A and floor(sqrt(d2)) is in B.
bool check(long long k, int max_A, int max_B) {
    // Find all divisors d1 of k up to sqrt(k).
    long long limit = isqrt(k);
   
    for (long long d1 = 1; d1 <= limit; ++d1) {
        if (k % d1 == 0) { // If d1 is a divisor of k
            long long d2 = k / d1; // The corresponding divisor d2
            
            // Calculate integer square roots
            long long sqrt_d1 = isqrt(d1);
            long long sqrt_d2 = isqrt(d2);
            
            // Check pair (d1, d2): Does d1 correspond to an A_i and d2 to a B_j?
            // Check if floor(sqrt(d1)) is a value present in deck A.
            // Use precomputed boolean array `hasA`. Index must be within bounds [1, MAX_VAL-1].
            // Also, the value must not exceed the maximum value actually present in A (max_A).
            bool d1_valid_for_A = (sqrt_d1 > 0 && sqrt_d1 <= max_A && sqrt_d1 < MAX_VAL && hasA[sqrt_d1]);
            
            if (d1_valid_for_A) {
                // Check if floor(sqrt(d2)) is a value present in deck B.
                 bool d2_valid_for_B = (sqrt_d2 > 0 && sqrt_d2 <= max_B && sqrt_d2 < MAX_VAL && hasB[sqrt_d2]);
                if (d2_valid_for_B) {
                    return true; // Found a valid representation for k
                }
            }

            // Check pair (d2, d1) if d1 != d2 (i.e., k is not a perfect square d1*d1)
            // Does d2 correspond to an A_i and d1 to a B_j?
            if (d1 * d1 != k) {
                 // Check if floor(sqrt(d2)) is a value present in deck A.
                 bool d2_valid_for_A = (sqrt_d2 > 0 && sqrt_d2 <= max_A && sqrt_d2 < MAX_VAL && hasA[sqrt_d2]);
                 
                 if (d2_valid_for_A) {
                     // Check if floor(sqrt(d1)) is a value present in deck B.
                     bool d1_valid_for_B = (sqrt_d1 > 0 && sqrt_d1 <= max_B && sqrt_d1 < MAX_VAL && hasB[sqrt_d1]);
                     if (d1_valid_for_B) {
                          return true; // Found a valid representation for k
                     }
                 }
            }
        }
    }
    // If no pair of divisors worked, k cannot be represented.
    return false; 
}


int main() {
    // Faster I/O
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int N, M; // Number of cards in decks A and B
    std::cin >> N >> M;

    // Initialize boolean arrays tracking card presence
    // This is implicitly done for global arrays, but good practice to be explicit if they were local.
    // std::fill(hasA, hasA + MAX_VAL, false);
    // std::fill(hasB, hasB + MAX_VAL, false);

    std::vector<int> A_vec(N); // Store A values to check A[0] later
    int max_A = 0; // Track the maximum value in deck A
    for (int i = 0; i < N; ++i) {
        std::cin >> A_vec[i];
        // Only consider positive values within the array bounds for hasA lookup table
        if (A_vec[i] > 0) { 
             if (A_vec[i] < MAX_VAL) {
                 hasA[A_vec[i]] = true; // Mark value as present in A
             }
             // Keep track of the maximum value regardless of array bounds
             if (A_vec[i] > max_A) max_A = A_vec[i]; 
        }
    }

    std::vector<int> B_vec(M); // Store B values
    int max_B = 0; // Track the maximum value in deck B
    for (int i = 0; i < M; ++i) {
        std::cin >> B_vec[i];
        if (B_vec[i] > 0) {
             if (B_vec[i] < MAX_VAL) {
                 hasB[B_vec[i]] = true; // Mark value as present in B
             }
             if (B_vec[i] > max_B) max_B = B_vec[i];
         }
    }

    // Handle the edge case where 1 cannot be formed.
    // This occurs if A does not contain 1, or B does not contain 1.
    // The smallest product xy would be A_1^2 * B_1^2. If A_1 > 1 or B_1 > 1, this product is > 1.
    // Check using the hasA/hasB arrays for presence of 1.
    if (!hasA[1] || !hasB[1]) {
         std::cout << 1 << std::endl; // If 1 cannot be formed, it's the smallest positive integer.
         return 0;
    }

    // Iterate through positive integers k starting from 1.
    // Find the first k that cannot be represented as a product xy.
    long long k = 1;
    while (true) {
        // Check if k can be represented.
        if (!check(k, max_A, max_B)) { 
            std::cout << k << std::endl; // Found the smallest integer not representable.
            return 0; // Exit program.
        }
        k += 1; // Check the next integer.
    }

    return 0; // Should not be reached due to the infinite loop and return inside.
}