#include <vector>
#include <numeric>
#include <algorithm>
#include <cmath>
// Khai báo hàm interactor
long long collisions(std::vector<long long> x);
namespace {
// Hàm kiểm tra xem N có nằm trong khoảng [1, limit] không.
// Sử dụng tính chất Difference Set: Tạo tập hợp S sao cho các hiệu số |x - y|
// bao phủ toàn bộ các số từ 1 đến limit.
// Nếu collisions(S) > 0 => tồn tại x, y sao cho |x - y| chia hết cho n.
// Vì max(|x-y|) ~ limit, điều này ngụ ý n <= limit.
// Chi phí: ~ 2 * sqrt(limit)
bool check(long long limit) {
if (limit < 1) return false;
// Chọn B ~ sqrt(limit)
long long B = std::sqrt(limit);
if (B * B < limit) B++;
std::vector<long long> s;
s.reserve(2 * B + 5);
// Phần 1: 1, 2, ..., B
for (long long i = 1; i <= B; ++i) s.push_back(i);
// Phần 2: B, 2B, 3B, ..., B*B
// Đảm bảo bao phủ đến limit
long long current = B;
while (current <= limit) { // Chỉ cần bao phủ đến limit là đủ
s.push_back(current);
current += B;
}
// Thêm một phần tử cuối để chắc chắn bao phủ phần dư nếu có
if (s.back() < limit) s.push_back(limit);
// Sort và Unique để tối ưu
std::sort(s.begin(), s.end());
s.erase(std::unique(s.begin(), s.end()), s.end());
return collisions(s) > 0;
}
// Hàm thực hiện Binary Search trên đáp án trong đoạn [L, R]
int binary_search_n(long long L, long long R) {
long long ans = R;
while (L <= R) {
long long mid = L + (R - L) / 2;
// Kiểm tra xem n có nằm trong [1, mid] không
if (check(mid)) {
ans = mid;
R = mid - 1; // Tìm kiếm kết quả nhỏ hơn
} else {
L = mid + 1; // n lớn hơn mid
}
}
return (int)ans;
}
}
int hack() {
// CHIẾN THUẬT: PHÂN TẦNG ĐỂ TỐI ƯU ĐIỂM SỐ
// Giai đoạn 1: Kiểm tra Subtask 1 & 2 (N <= 1,000,000)
// Chi phí check(10^6) chỉ khoảng 2000 query. Rất rẻ.
// Nếu N nằm trong vùng này, ta Binary Search tốn rất ít chi phí -> Ăn trọn điểm 2 subtask đầu.
if (check(1000000)) {
return binary_search_n(1, 1000000);
}
// Giai đoạn 2: N > 1,000,000 (Subtask 3)
// Ta Binary Search trên vùng còn lại [10^6 + 1, 10^9].
// Chi phí sẽ là tổng chuỗi log * sqrt(mid).
return binary_search_n(1000001, 1000000000);
}
