本文共 3369 字，大约阅读时间需要 11 分钟。

分在一组的前提是,任意两个数都互质

考虑预处理一个$f[i]$表示$[i+1,f_i-1]$的所有数和$a_i$互质,且$f_i$最大

这样我们就能得到$st[i]$表示$[i,s{t}_i-1]$能分成一组而且最长

$st[i]=\underset{j=i}{\overset{f_i-1}{\min }}\{$

这个很好理解,虽然自己最远能到达$f_i-1$,但是还需要考虑其他数字的限制

但是暴力枚举复杂度爆炸

考虑对$a_i$来说,存在因子$x_1,x_2...x_k$

那么只需要满足组内的数没有这些因子就好了!!!

我们从$n$往$1$倒序枚举$a_i$,分解质因子,并刷新每种因子出现的最早位置,记$nxt[x]$表示质因子$x$出现在索引$i$后的最早位置

那么$f[i]=min(f[i],nx[x_j])$,其中$x_j$是$a_i$的一个因子

这样我们可以得到$f$数组,套一个区间最小值的数据结构可以得到$st$数组

但是发现$st[i]=\underset{j=i}{\overset{f_i-1}{\min }}\{$

而$f$数组是单调递增的,所以不用数据结构,只需要让$f_i$去更新$f_{i-1}$即可

然后我们对于询问$[l,r]$

每次从$l$跳到$st[l]$,最后看看超过$r$时跳了多少次即可。

但是会超时

没关系,倍增一下$st$数组即可,也就是预处理$st[i][k]$

表示从$i$跳$2^k$步最远能到达哪里

版本一

比赛时憨憨套了线段树求$f$数组的区间最小值

#include 
   
    using namespace std;#define mid (l+r>>1)#define ls (rt<<1)#define rs (rt<<1|1)#define lson ls,l,mid#define rson rs,mid+1,rconst int maxn = 1e6+10;int a[maxn],n,q;vector
    
     zhi[maxn];void make(){
   	for(int i=2;i<=100000;i++)	for(int j=i;j<=100000;j+=i )		zhi[j].push_back( i );}int nxt[maxn],mi[maxn],su[maxn];void build(int rt,int l,int r){
   	if( l==r ){
    su[rt] = mi[l]; return; }	build( lson ); build( rson );	su[rt] = min( su[ls],su[rs] );}int ask(int rt,int l,int r,int L,int R){
   	if( l>R || r
     
      =L&&r<=R )	return su[rt];	return min( ask(lson,L,R),ask(rson,L,R) );}int st[maxn][22];void init(){
   	for(int i=1;i<=100000;i++)	mi[i] = nxt[i] = n+1;	for(int i=n;i>=1;i--)	for( auto v:zhi[a[i]] )	{
   		mi[i] = min( mi[i],nxt[v] );		nxt[v] = i;	}	build(1,1,n);		memset( st,20,sizeof st );	for(int i=1;i<=n;i++)	st[i][0] = ask(1,1,n,i,mi[i]-1 );	for(int i=1;i<=20;i++)	for(int j=1;j+(1<
      
       <=n;j++)	{
   		int nx = st[j][i-1];		if( nx>n+1 )	st[j][i] = nx;		else	st[j][i] = st[nx][i-1]; 	}}void solve(int l,int r){
   	int ans = 0;	for(int i=20;i>=0;i--)		if( st[l][i]<=r )	l = st[l][i],ans += (1<
       
        > n >> q;	for(int i=1;i<=n;i++)	cin >> a[i];	make(); init();	while( q-- )	{
   		int l,r; scanf( "%d%d",&l,&r);		solve(l,r);	}}
       
      
     
    
   

最小值扫一遍就好了

版本二

#include 
   
    using namespace std;const int maxn = 1e6+10;int a[maxn],n,q;vector
    
     zhi[maxn];void make(){
   	for(int i=2;i<=100000;i++)	for(int j=i;j<=100000;j+=i )		zhi[j].push_back( i );}int nxt[maxn],mi[maxn];int st[maxn][22];void init(){
   	for(int i=1;i<=100000;i++)	mi[i] = nxt[i] = n+1;	for(int i=n;i>=1;i--)	{
   		for( auto v:zhi[a[i]] )		{
   			mi[i] = min( mi[i],nxt[v] );			nxt[v] = i;		}		mi[i-1] = mi[i];	}	memset( st,20,sizeof st );	for(int i=1;i<=n;i++)	st[i][0] = mi[i];	for(int i=1;i<=20;i++)	for(int j=1;j+(1<
     
      <=n;j++)	{
   		int nx = st[j][i-1];		if( nx>n+1 )	st[j][i] = nx;		else	st[j][i] = st[nx][i-1]; 	}}void solve(int l,int r){
   	int ans = 0;	for(int i=20;i>=0;i--)		if( st[l][i]<=r )	l = st[l][i],ans += (1<
      
       > n >> q;	for(int i=1;i<=n;i++)	cin >> a[i];	make(); init();	while( q-- )	{
   		int l,r; scanf( "%d%d",&l,&r);		solve(l,r);	}}
      
     
    
   

转载地址：https://issue-is-vegetable.blog.csdn.net/article/details/116008483 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！