### fluxgamer999's blog

By fluxgamer999, history, 5 weeks ago,

[submission:257656771][problem:1547F] The Maximum Number of Operation we Need is N : so we do binary search On ans the element at ith index at kth step will be gcd of range (i,k) for range gcd i used segTree.

int n ;
cin >> n  ;
vector<int> a(2 * n);
for (int i = 0 ; i < n ; i++) {
cin >> a[i];
}
for (int i = 0 ; i < n ; i++) {
a[n + i] = a[i];
}
int temp = 2 * n ;
int temp2 = 2 * n ;
while ((temp2) & (temp2 - 1)) {
temp2++;
a.pb(0);
}
vector<int> seg(2 * temp2);
for (int i = 0 ; i < temp2 ; i++) {
seg[temp2 + i] = a[i];
}
for (int i = temp2 - 1 ; i >= 1; i--) {
seg[i] = __gcd(seg[2 * i], seg[2 * i + 1]);
}
auto query = [&](int l , int r) {
l += temp2;
r += temp2;
int ans = 0 ;
while (l < r) {
if (l & 1) ans = __gcd(ans, seg[l++]);
if (r & 1) ans = __gcd(ans, seg[--r]);
l /= 2; r /= 2;
}
return ans ;
};
debug(a);
auto check = [&](int mid) {
set<int> s ;
for (int i = 0 ; i < n ; i++) {
int r = i + mid + 1  ;
// 	cout << i << " " << r << " " << query(i, r) << endl;
s.insert(query(i, r));
}
return (s.size() == 1);
};
int lo = 0 ;
int hi = n  ;
int ans = 0 ;
while (lo <= hi) {
int mid  =  (hi + lo) / 2 ;
if (check(mid)) {
ans = mid ;
hi = mid - 1 ;
}
else {
lo = mid + 1 ;
}
}
cout << ans << endl;

• -1