QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#749671#9426. Relearn through ReviewTJUHuangTaoWA 6ms9000kbC++201.7kb2024-11-15 09:04:582024-11-15 09:04:58

Judging History

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

  • [2024-11-15 09:04:58]
  • 评测
  • 测评结果:WA
  • 用时:6ms
  • 内存:9000kb
  • [2024-11-15 09:04:58]
  • 提交

answer

#include <bits/stdc++.h>
// #define int long long
#define inf 0x3f3f3f3f
#define ll long long
#define pii pair<int, int>
#define tii tuple<int, int, int>
#define db double
#define all(a) a.begin(), a.end()
using namespace std;
const int maxn = 3e5 + 10;
const int mod = 998244353;
int lg[maxn], pre[maxn], suf[maxn], arr[maxn], n, k;
struct STtable {
    int st[maxn][20];
    void init() {
        for (int j = 1; j < 20; j++)
            for (int i = 1; i + (1 << j) - 1 < n; i++)
                st[i][j] = __gcd(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
    }
    int query(int l, int r) {
        if (l > r) return 0;
        int k = lg[r - l + 1];
        return __gcd(st[l][k], st[r - (1 << k) + 1][k]);
    }
} ST;
void solve() {
    cin >> n >> k;
    for (int i = 1; i <= n; i++) cin >> arr[i];
    pre[0] = suf[n + 1] = 0;
    for (int i = 1; i <= n; i++) pre[i] = __gcd(arr[i], pre[i - 1]);
    for (int i = n; i; i--) suf[i] = __gcd(arr[i], suf[i + 1]);
    for (int i = 1; i < n; i++) ST.st[i][0] = abs(arr[i] - arr[i + 1]);
    ST.init();
    int ans = 1;
    for (int i = 1; i <= n; i++) {
        if (pre[i] != pre[i - 1]) {
            for (int j = i; j <= n; j++) {
                int gcd = __gcd(pre[i - 1], suf[j + 1]);
                gcd = __gcd(gcd, arr[j] + k);
                gcd = __gcd(gcd, ST.query(i, j - 1));
                ans = max(ans, gcd);
            }
        }
    }
    cout << ans << "\n";
}
signed main() {
    // freopen("1.in", "r", stdin);
    // freopen("1.out", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    for (int i = 2; i < maxn; i++) lg[i] = lg[i >> 1] + 1;
    int t = 1;
    cin >> t;
    while (t--) solve();
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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
Wrong Answer
time: 6ms
memory: 6956kb

input:

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

output:

1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
...

result:

wrong answer 1st lines differ - expected: '641766957852455745', found: '1'