QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#698129#9426. Relearn through ReviewMiguel03121WA 93ms3608kbC++171.4kb2024-11-01 17:35:272024-11-01 17:35:28

Judging History

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

  • [2024-11-01 17:35:28]
  • 评测
  • 测评结果:WA
  • 用时:93ms
  • 内存:3608kb
  • [2024-11-01 17:35:27]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

#define F(i, a, b) for (int i = a; i < b; i++)
#define ALL(x) x.begin(), x.end()
#define IOS ios_base::sync_with_stdio(0)

typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef long long ll;

vector<ll> a;
ll n, k;

bool valid(int index, ll g, bool opened, bool closed) {
  if (index >= n) {
    return true;
  }

  bool ans = false;
  if (a[index] % g == 0) {
    if (opened) {
      ans |= valid(index + 1, g, true, true);
    } else {
      ans |= valid(index + 1, g, false, false);
    }
  }
  if ((a[index] + k) % g == 0 && !closed) {
    ans |= valid(index + 1, g, true, false);
  }

  return ans;
}

int main() {
  IOS;
  cin.tie(0), cout.tie(0);
  int t;
  cin >> t;
  while (t--) {
    cin >> n >> k;
    a = vector<ll>(n);
    F(i, 0, n) { cin >> a[i]; }
    if (n == 1) {
      cout << a[0] + k << '\n';
      continue;
    }
    ll ans = 1;
    ll g = gcd(a[0], a[1]);
    if (valid(2, g, false, false)) {
      ans = max(ans, g);
    }
    g = gcd(a[0] + k, a[1]);
    if (valid(2, g, true, true)) {
      ans = max(ans, g);
    }
    g = gcd(a[0], a[1] + k);
    if (valid(2, g, true, false)) {
      ans = max(ans, g);
    }
    g = gcd(a[0] + k, a[1] + k);
    if (valid(2, g, true, false)) {
      ans = max(ans, g);
    }
    cout << ans << '\n';
  }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 93ms
memory: 3572kb

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
182894211060271407
880411769063535667
560553564512176618
183698346865682381
962990836390050009
616597869896951268
878097339332572161
188820994675344528
997057718507559252
949074379610491450
37337367838628559
632093288650732211
3771217139073309...

result:

wrong answer 58th lines differ - expected: '143096853751349666', found: '1'