結果
| 問題 |
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.
}