QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#227383 | #7322. Random Numbers | FLself | TL | 0ms | 0kb | C++20 | 3.4kb | 2023-10-27 13:46:42 | 2023-10-27 13:46:42 |
answer
/*
[[ ⣇⣿⠘⣿⣿⣿⡿⡿⣟⣟⢟⢟⢝⠵⡝⣿⡿⢂⣼⣿⣷⣌⠩⡫⡻⣝⠹⢿⣿⣷ ]],
[[ ⡆⣿⣆⠱⣝⡵⣝⢅⠙⣿⢕⢕⢕⢕⢝⣥⢒⠅⣿⣿⣿⡿⣳⣌⠪⡪⣡⢑⢝⣇ ]],
[[ ⡆⣿⣿⣦⠹⣳⣳⣕⢅⠈⢗⢕⢕⢕⢕⢕⢈⢆⠟⠋⠉⠁⠉⠉⠁⠈⠼⢐⢕⢽ ]],
[[ ⡗⢰⣶⣶⣦⣝⢝⢕⢕⠅⡆⢕⢕⢕⢕⢕⣴⠏⣠⡶⠛⡉⡉⡛⢶⣦⡀⠐⣕⢕ ]],
[[ ⡝⡄⢻⢟⣿⣿⣷⣕⣕⣅⣿⣔⣕⣵⣵⣿⣿⢠⣿⢠⣮⡈⣌⠨⠅⠹⣷⡀⢱⢕ ]],
[[ ⡝⡵⠟⠈⢀⣀⣀⡀⠉⢿⣿⣿⣿⣿⣿⣿⣿⣼⣿⢈⡋⠴⢿⡟⣡⡇⣿⡇⡀⢕ ]],
[[ ⡝⠁⣠⣾⠟⡉⡉⡉⠻⣦⣻⣿⣿⣿⣿⣿⣿⣿⣿⣧⠸⣿⣦⣥⣿⡇⡿⣰⢗⢄ ]],
[[ ⠁⢰⣿⡏⣴⣌⠈⣌⠡⠈⢻⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣬⣉⣉⣁⣄⢖⢕⢕⢕ ]],
[[ ⡀⢻⣿⡇⢙⠁⠴⢿⡟⣡⡆⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⣵⣵⣿ ]],
[[ ⡻⣄⣻⣿⣌⠘⢿⣷⣥⣿⠇⣿⣿⣿⣿⣿⣿⠛⠻⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿ ]],
[[ ⣷⢄⠻⣿⣟⠿⠦⠍⠉⣡⣾⣿⣿⣿⣿⣿⣿⢸⣿⣦⠙⣿⣿⣿⣿⣿⣿⣿⣿⠟ ]],
[[ ⡕⡑⣑⣈⣻⢗⢟⢞⢝⣻⣿⣿⣿⣿⣿⣿⣿⠸⣿⠿⠃⣿⣿⣿⣿⣿⣿⡿⠁⣠ ]],
[[ ⡝⡵⡈⢟⢕⢕⢕⢕⣵⣿⣿⣿⣿⣿⣿⣿⣿⣿⣶⣶⣿⣿⣿⣿⣿⠿⠋⣀⣈⠙ ]],
[[ ⡝⡵⡕⡀⠑⠳⠿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠿⠛⢉⡠⡲⡫⡪⡪⡣ ]],
*/
#include<bits/stdc++.h>
using i64 = long long;
i64 exgcd(i64 a, i64 b, i64& x, i64& y) {
if (a == 0) {
x = 0, y = 1;
return b;
}
i64 ret = exgcd(b % a, a, x, y), xx = x;
x = y - b / a * x;
y = xx;
return ret;
}
void solv() {
int n;
std::cin >> n;
std::vector<i64> a(n), b(n);
for (int i = 0; i < n; ++i) {
std::cin >> a[i];
}
for (int i = 0; i < n; ++i) {
std::cin >> b[i];
}
std::sort(b.begin(), b.end());
auto check=[&](i64 m, i64 k) {
std::vector<i64> c(n);
for (int i = 0; i < n; ++i) {
c[i] = (a[i] + k) % m;
}
std::sort(a.begin(), a.end());
for (int i = 0; i < n; ++i) {
if (b[i] != c[i]) return false;
}
return true;
};
auto weak_check=[&](i64 m, i64 k) {
for (int i = 0; i < n; ++i) {
if (!std::binary_search(b.begin(), b.end(), (a[i] + k) % m)) {
return false;
}
}
return true;
};
i64 min_m = *std::max_element(b.begin(), b.end()) + 1;
i64 max_m = *std::max_element(a.begin(), a.end()) + 1;
__int128 sum_a = 0, sum_b = 0;
for (int i = 0; i < n; ++i) {
sum_a += a[i];
sum_b += b[i];
}
for (i64 m = min_m; m <= max_m; ++m) {
i64 k, _;
i64 g = exgcd(n, m, k, _);
i64 s = (sum_a - sum_b) % m;
s = (s + m) % m;
if (s % g) continue;
for (i64 kk = 0; kk < g; ++kk) {
i64 x = (k + m / g * kk) % m * (s / g) % m;
std::cerr << m << ' ' << x << '\n';
if (weak_check(m, x) && check(m, x)) {
std::cout << m << ' ' << x << '\n';
return;
}
}
}
}
signed main() {
std::ios::sync_with_stdio(false), std::cin.tie(nullptr), std::cout.tie(nullptr);
int tt = 1;
// std::cin >> tt;
while (tt--) {
solv();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Time Limit Exceeded
input:
100000 567521362129079894 696655062397105489 618592056868108007 305121979898345388 418241613626143516 566981041096909436 687040795047811890 413478956193714535 294233239559482609 517064297715474906 919243760085177084 146712184879435114 334896924897329674 808181231522418580 201231480069623536 26529430...