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