QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#742916#9426. Relearn through ReviewfosovTL 0ms3696kbC++141.6kb2024-11-13 17:38:352024-11-13 17:38:37

Judging History

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

  • [2024-11-13 17:38:37]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:3696kb
  • [2024-11-13 17:38:35]
  • 提交

answer

#include "bits/stdc++.h"
using namespace std;

#define ll long long 
#define INF 0x3f3f3f3f
#define LNF 0x3f3f3f3f3f3f3f3fll
#define MOD 998244353
#define pii pair<int, int>

#define N 100010
#define K 20

vector<int> factors(int x) {
    vector<int> res;
    int s = sqrt(x);
    for (int i = 1; i <= s; ++ i) {
        if (x % i == 0) {
            res.emplace_back(i);
            if (x/i != i) res.emplace_back(x/i);
        }
    }
    return res;
}

ll gcd(ll a, ll b) {
    return b == 0 ? a : gcd(b, a % b);
}

int main() {
#ifdef TEST
    freopen("zz.in", "r+", stdin);
#endif
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int t; cin >> t;
    while (t --) {
        ll n, k; cin >> n >> k;
        vector<ll> a(n+5);
        for (int i = 1; i <= n; ++ i) cin >> a[i];

        auto ok = [&](ll x) {
            int lb = -1, rb = -1, cnt = 0;
            for (int i = 1, j = 1; i <= n; ++ i) {
                if (a[i] % x == 0) continue;
                while (j <= i || (j <= n && (a[j] % x != 0))) ++ j;
                lb = i, rb = j, ++ cnt;
                i = j - 1;
            }

            int res = cnt == 1;
            for (int i = lb; i < rb; ++ i) res &= (a[i] + k) % x == 0;
            return res;
        };

        ll res = a[1] + k;
        for (int i = 1; i <= n; ++ i) res = gcd(res, a[i] + k);

        set<int> s;
        for (int i = 1; i <= n; ++ i) {
            for (auto x : factors(a[i])) {
                s.insert(x);
            }
        }

        for (auto x : s) if (ok(x)) res = max(res, 1ll * x);
        cout << res << '\n';
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3696kb

input:

2
6 2
5 3 13 8 10 555
3 0
3 6 9

output:

5
3

result:

ok 2 lines

Test #2:

score: -100
Time Limit Exceeded

input:

100000
1 608611451460421713
33155506392034032
1 743116173559300609
6138108577573005
7 364454564010802125
657035115675878115 657035115675878115 657035115675878115 657035115675878115 657035115675878115 292580551665075990 657035115675878115
4 316648374341335221
365788422120542814 182894211060271407 731...

output:

641766957852455745
749254282136873614
15
3
1
560553564512176618
1
3
616597869896951268
6
188820994675344528
997057718507559252
949074379610491450
2
1
1
356502546608886970
789177332497135009
2
2
134561004312215460
1
3
1
1
649630151112107049
1
815531812998319264
1
2
635489507937409521
10
6255828253857...

result: