社区讨论
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 条回复,欢迎继续交流。
正在加载回复...