QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#749671 | #9426. Relearn through Review | TJUHuangTao | WA | 6ms | 9000kb | C++20 | 1.7kb | 2024-11-15 09:04:58 | 2024-11-15 09:04:58 |
Judging History
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'