F. Array Stabilization (GCD version)
题意：
给t组样例
(t <= 1e4)
每组样例给n
a[1] , a[2] , ...... a[n]
(a[i] <= 1e6 , n <= 2e5)
定义一个新数组b[]数组
b数组等于gcd(a[i],a[(i+1)%n])
然后把b复制给a
问最少复制多少次使得a数组中的所有数都相等
思路：
我们可以发现
第1次操作之后
b[1] = gcd(a[1],a[2])
第2次操作之后
b[1] = gcd(a[1],a[2],a[3])
........
第n-1次操作之后
b[1] = gcd(a[1],a[2],a[3],.....a[n])
也就是说 经过x次操作之后
b[i] = gcd(a[i],a[i+1],a[i+2],......a[i+x])
也就是说 最多n-1次操作之后
一定可以使得a数组中的数都相等
那么很明显可以二分操作
假设当前操作为mid
如果在mid次操作中可以使得所有a[i]都相等
说明可以把mid变小
即r = mid
否则可以让
l = mid
查询区间最大公约数可以线段树或者st表
我这里用的是线段树
线段树时间复杂度nlogn
二分时间复杂度logn
所以整体时间复杂度nlognlogn
这题给了4s
所以是可以过的
一点题外话
最后25min想到了二分
但是不知道怎么查询区间最大公约数
最后5min想到了线段树
可惜为时已晚
时间复杂度：O nlognlogn
#include<bits/stdc++.h>
#define fer(i,a,b) for(re i = a ; i <= b ; ++ i)
#define re register int
#define pll pair<int,int>
#define x first
#define y second
#define sf(x) scanf("%d",&x)
#define sfl(x) scanf("%lld",&x)
typedef long long ll ;
using namespace std;
const int N = 1e6 + 10 , M = 1010 , inf = 0x3f3f3f3f , mod = 1e9 + 7 ;
int t ;
int n ;
int a[N] ;
int s[N] ;
struct Node
{
int l, r;
ll sum, d;
}tr[N * 4];
ll gcd(ll a, ll b)
{
return b ? gcd(b, a % b) : a;
}
void pushup(Node &u, Node &l, Node &r)
{
u.sum = l.sum + r.sum;
u.d = gcd(l.d, r.d);
}
void pushup(int u)
{
pushup(tr[u], tr[u << 1], tr[u << 1 | 1]);
}
void build(int u, int l, int r)
{
if (l == r)
{
ll b = a[r] - a[r - 1];
tr[u] = {l, r, b, b};
}
else
{
tr[u].l = l, tr[u].r = r;
int mid = l + r >> 1;
build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
pushup(u);
}
}
void modify(int u, int x, ll v)
{
if (tr[u].l == x && tr[u].r == x)
{
ll b = tr[u].sum + v;
tr[u] = {x, x, b, b};
}
else
{
int mid = tr[u].l + tr[u].r >> 1;
if (x <= mid) modify(u << 1, x, v);
else modify(u << 1 | 1, x, v);
pushup(u);
}
}
Node query(int u, int l, int r)
{
if (tr[u].l >= l && tr[u].r <= r) return tr[u];
else
{
int mid = tr[u].l + tr[u].r >> 1;
if (r <= mid) return query(u << 1, l, r);
else if (l > mid) return query(u << 1 | 1, l, r);
else
{
auto left = query(u << 1, l, r);
auto right = query(u << 1 | 1, l, r);
Node res;
pushup(res, left, right);
return res;
}
}
}
// scanf("%s%d%d", op, &l, &r);
// if (*op == 'Q')
// {
// auto left = query(1, 1, l);
// Node right({0, 0, 0, 0});
// if (l + 1 <= r) right = query(1, l + 1, r);
// printf("%lld
", abs(gcd(left.sum, right.d)));
// }
bool check(int mid)
{
map<int,int> q ;
for(int i = 1 ; i <= n ; i ++)
{
int l = i , r = i + mid ;
auto left = query(1, 1, l);
Node right({0, 0, 0, 0});
if (l + 1 <= r) right = query(1, l + 1, r);
q[abs(gcd(left.sum, right.d))] ++ ;
}
return q.size() == 1 ;
}
int main()
{
cin >> t ;
while(t--)
{
cin >> n ;
fer(i,1,n)
{
sf(a[i]) ;
a[i + n] = a[i] ;
}
build(1, 1, 2 * n);
int l = 0 , r = n - 1 ;
while(l < r)
{
int mid = r + l >> 1 ;
if(check(mid)) r = mid ;
else l = mid + 1 ;
}
cout << l << "
" ;
}
return 0;
}