QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#661476 | #9426. Relearn through Review | ShwStone | TL | 0ms | 3924kb | C++14 | 2.7kb | 2024-10-20 16:25:45 | 2024-10-20 16:25:45 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int MAXN(1e5 + 5);
int n;
long long k;
long long a[MAXN];
vector<pair<long long, int>> p;
map<pair<int, int>, long long> mp, tmp;
void calcP(long long v) {
p.clear();
for (long long i = 2; i * i <= v; i++) {
int t = 0;
while (v % i == 0) {
v /= i;
t++;
}
if (t) p.emplace_back(i, t);
}
if (v > 1) p.emplace_back(v, 1);
}
long long gcd(long long x, long long y) {
while (x ^= y ^= x ^= y %= x);
return y;
}
long long calc1n() {
for (int i = 1; i <= n; i++) a[i] += k;
long long res = a[1];
for (int i = 2; i <= n; i++) res = gcd(res, a[i]);
for (int i = 1; i <= n; i++) a[i] -= k;
return res;
}
void calc(int cnt, long long v) {
tmp.clear();
long long tv = v;
while (cnt--) {
if (k % v == 0) {
bool flag = true;
for (int i = 1; i <= n; i++) {
if (a[i] % v != 0) {
flag = false;
break;
}
}
if (flag) {
tmp[make_pair(-1, -1)] = max(tmp[make_pair(-1, -1)], v);
}
} else {
int l = 0, r = 0;
bool flag = true;
for (int i = 1; i <= n; i++) {
if (a[i] % v != 0) {
if ((a[i] + k) % v != 0) {
flag = false;
break;
}
if (!l) l = i;
else if (r) {
flag = false;
break;
}
} else {
if (l && !r) r = i - 1;
}
}
if (flag) {
if (l) {
if (!r) r = n;
tmp[make_pair(l, r)] = max(tmp[make_pair(l, r)], v);
} else {
tmp[make_pair(0, 0)] = max(tmp[make_pair(0, 0)], v);
}
}
v *= tv;
}
}
long long ry = tmp.count(make_pair(-1, -1)) ? tmp[make_pair(-1, -1)] : 1;
for (auto x : tmp) {
if (x.first != make_pair(-1, -1)) {
x.second /= ry;
}
if (mp.count(x.first)) {
mp[x.first] *= x.second;
} else {
mp[x.first] = x.second;
}
}
}
long long calc1() {
calcP(a[1]);
mp.clear();
for (auto x : p) {
calc(x.second, x.first);
}
long long ry = mp.count(make_pair(-1, -1)) ? mp[make_pair(-1, -1)] : 1;
long long res = 1;
for (auto &x : mp) {
if (x.first != make_pair(-1, -1)) x.second *= ry;
res = max(res, x.second);
}
return res;
}
long long calcn() {
calcP(a[n]);
mp.clear();
for (auto x : p) {
calc(x.second, x.first);
}
long long ry = mp.count(make_pair(-1, -1)) ? mp[make_pair(-1, -1)] : 1;
long long res = 1;
for (auto &x : mp) {
if (x.first != make_pair(-1, -1)) x.second *= ry;
res = max(res, x.second);
}
return res;
}
void solve() {
scanf("%d %lld", &n, &k);
for (int i = 1; i <= n; i++) {
scanf("%lld", a + i);
}
long long ans = max({calc1n(), calc1(), calcn()});
printf("%lld\n", ans);
}
int main() {
int _;
scanf("%d", &_);
while (_--) {
solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3924kb
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...