社区讨论

WA on #2 求调

P14221 [ICPC 2024 Kunming I] 学而时习之参与者 2已保存回复 2

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
2 条
当前快照
1 份
快照标识符
@mhj1ssn7
此快照首次捕获于
2025/11/03 19:19
4 个月前
此快照最后确认于
2025/11/03 19:19
4 个月前
查看原帖
CPP
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>

using namespace std;
typedef long long ll;

const int N = 3e5 + 10;
ll k, a[N], b[N], pre[N], g[N][20], ans;
vector<ll> v; int t, n, lg2[N];

ll f(int l, int r){
	if(l > r) return 0;
	int lenlg = lg2[r-l+1];
	return __gcd(g[l][lenlg], g[r-(1 << lenlg) + 1][lenlg]);
}

int main(){
	cin >> t;
	while(t--){
		cin >> n >> k; lg2[0] = -1;
		v.clear(); ans = 1;
		for(int i = 1; i <= n; i++){
			cin >> a[i]; b[i] = a[i];
			pre[i] = __gcd(a[i], pre[i-1]);
			lg2[i] = lg2[i >> 1] + 1;
			g[i][0] = a[i] - a[i-1];
		}
		b[n+1] = 0;
		for(int i = n; i >= 2; i--) a[i] -= a[i-1];
		for(int j = 1; j < 20; j++){
			for(int i = 1; i + (1 << j) - 1 <= n; i++){
				g[i][j] = __gcd(g[i][j-1], g[i+(1<<(j-1))][j-1]);
			}
		}
		v.push_back(1);
		for(int i = 2; i <= n; i++){
			if(pre[i] < pre[i-1]) v.push_back(i);
		}
//		for(int i = 1; i <= n; i++){
//			cout << a[i] << ' ';
//		}
//		cout << '\n';
		ans = abs(__gcd(b[1] + k, f(2, n-1)));
		ll cnt = 0, ed = 0;
		for(int i = n+1; i >= 2; i--){
			ed = __gcd(ed, b[i]);
			cnt = __gcd(b[i-1]+k, ed);
//			cout << i << ' ' << b[i] << ' ' << b[i-1]+k << ' ' << cnt << '\n';
			for(ll j: v){
//				cout << i << ' ' << j << ' ' << __gcd(pre[j-1], f(j+1, i-1)) << '\n';
				ans = max(ans, abs(__gcd(__gcd(pre[j-1], f(j+1, i-1)), cnt)));
			}
		}
		cout << ans << '\n';
	}
	return 0;
}
//l=2, r=4

回复

2 条回复,欢迎继续交流。

正在加载回复...