QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#661476#9426. Relearn through ReviewShwStoneTL 0ms3924kbC++142.7kb2024-10-20 16:25:452024-10-20 16:25:45

Judging History

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

  • [2024-10-20 16:25:45]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:3924kb
  • [2024-10-20 16:25:45]
  • 提交

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...

output:


result: