QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#624573#9426. Relearn through ReviewDung1604RE 0ms3848kbC++143.3kb2024-10-09 16:08:592024-10-09 16:08:59

Judging History

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

  • [2024-10-09 16:08:59]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:3848kb
  • [2024-10-09 16:08:59]
  • 提交

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 = 1;
	
	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 + 1);
			if (find == second[y].end())continue;

			int posR = *second[y].lower_bound(i + 1)-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: 3848kb

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
Runtime Error

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

result: