QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#624619 | #9426. Relearn through Review | Dung1604 | WA | 180ms | 3868kb | C++17 | 3.3kb | 2024-10-09 16:15:59 | 2024-10-09 16:15:59 |
Judging History
answer
#include <iostream>
#include <queue>
#include <set>
#include <stack>
#include <utility>
#include <tuple>
#include <iomanip>
#include <map>
#include <algorithm>
#include <math.h>
#include <string>
#include <vector>
#include <unordered_map>
#define ll long long
#define inf 10000000000007
#define mod 1000000007
using namespace std;
const int BLOCK = 450;
ll fastpow(ll n, ll x) {
if (x == 0) {
return 1;
}
else {
ll ret = fastpow(n, x / 2);
ret = ((ret % mod) * (ret % mod)) % mod;
if (x % 2 == 0) {
return ret;
}
else {
return ((ret) * (n)) % mod;
}
}
}
ll gcd(ll a, ll b) {
if (b == 0) {
return a;
}
else {
return gcd(b, a % b);
}
}
ll lcm(ll a, ll b) {
ll val = (a % mod * b % mod) % mod;
val = (val * fastpow(gcd(a, b), mod - 2)) % mod;
return val;
}
int Logk(ll n, ll k) {
if (k == 1) {
return 1;
}
if (n == 0) {
return 0;
}
int count = -1;
while (n > 0) {
count++;
n /= k;
}
return count;
}
struct Dsu {
vector<int> par;
void init(int n) {
par.resize(n + 5, 0);
for (int i = 1; i <= n; i++) par[i] = i;
}
int find(int u) {
if (par[u] == u) return u;
return par[u] = find(par[u]);
}
bool join(int u, int v) {
u = find(u); v = find(v);
if (u == v) return false;
par[v] = u;
return true;
}
} dsu;
ll dp[300005][35];
void solve() {
ll n, k;
cin >> n >> k;
vector<ll> a(n + 1);
vector<ll> b(n + 1);
vector<ll> prefix(n + 1);
set<ll> sufix;
map<ll, set<int>> second;
for (int i = 1; i <= n; i++) {
cin >> a[i];
b[i] = abs(a[i] - a[i - 1]);
}
prefix[1] = a[1];
for (int i = 2; i <= n; i++) {
prefix[i] = gcd(prefix[i - 1], a[i]);
}
for (int i = 1; i <= n; i++) {
dp[i][0] = b[i];
}
if (k == 0) {
cout << prefix[n] << endl;
return;
}
else {
bool equal = true;
for (int i = 2; i <= n; i++) {
if (a[i] != a[1]) {
equal = false;
break;
}
}
if (equal) {
cout << a[1] + k << endl;
return;
}
}
for (int j = 1; j < 25; j++) {
for (int i = 1; i <= n; i++) {
if (i + (1 << j) - 1 <= n) {
dp[i][j] = gcd(dp[i][j - 1], dp[i + (1 << (j - 1))][j - 1]);
}
}
}
ll cur = a[n];
sufix.insert(cur);
second[cur].insert(n);
for (int i = n - 1; i >= 1; i--) {
cur = gcd(cur, a[i]);
second[cur].insert(i);
sufix.insert(cur);
}
ll ans = prefix[n];
for (int i = 1; i <= n; i++) {
ll x = prefix[i];
if (x == 1) {
break;
}
for (auto it = sufix.begin(); it != sufix.end(); it++) {
ll y = *it;
ll p = gcd(x, y);
if (p == 1)continue;
int posL = i + 1;
auto find = second[y].lower_bound(i + 2);
if (find == second[y].end())continue;
int posR = *find-1;
if (posR == posL) {
ans = max(ans, p);
}
else {
ll log = Logk(posR - posL, 2);
ll mid = gcd(dp[posL + 1][log], dp[posR - (1 << log) + 1][log]);
p = gcd(mid, p);
if ((a[posL] + k) % p == 0) {
ans = max(ans, gcd(mid, p));
}
}
}
}
cout << ans << endl;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int t;
cin >> t;
while (t--) {
solve();
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3556kb
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: 180ms
memory: 3868kb
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 657035115675878115 3 1 560553564512176618 2 1 616597869896951268 3 188820994675344528 997057718507559252 949074379610491450 37337367838628559 632093288650732211 1 366861733803058826 789177332497135009 1 1 134561004312215460 1 1 1 809535299113892268 6496301511121...
result:
wrong answer 4th lines differ - expected: '182894211060271407', found: '3'