QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#227378#7322. Random NumbersFLselfTL 0ms0kbC++203.1kb2023-10-27 13:43:352023-10-27 13:43:35

Judging History

你现在查看的是最新测评结果

  • [2023-10-27 13:43:35]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:0kb
  • [2023-10-27 13:43:35]
  • 提交

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;
    };

    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 (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...

output:


result: