自动搬运

查看原文

来自洛谷，原作者为

	大头 YSGH牛逼

搬运于2025-08-24 22:13:01，当前版本为作者最后更新于2019-11-13 20:00:26，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

算法1

我们尝试将$lcm_{l,r}$表示为$r-l+1$个数字$b_i$的乘积，其中$b_i|a_i$。

考虑加入一个数字$a_{r+1}$，则我们需要求出$gcd(\Pi b_i,a_{r+1})$。这可以使用取模很方便的实现。

每次询问可以暴力插入所有$r-l+1$个数字。

时间复杂度$O(Tn^3)$。

code:

#include<bits/stdc++.h>
#define For(i,j,k) for (int i=(int)(j);i<=(int)(k);i++)
#define Rep(i,j,k) for (int i=(int)(j);i>=(int)(k);i--)
#define ll long long
using namespace std;
const int N=505;
const int mo=1000000007;
int n,Q;
ll a[505],b[505];
ll gcd(ll x,ll y){
	return y?gcd(y,x%y):x;
}
void solve(){
	scanf("%d%d",&n,&Q);
	For(i,1,n) scanf("%lld",&a[i]);
	while (Q--){
		int l,r,ans=1;
		scanf("%d%d",&l,&r);
		For(i,l,r){
			b[i]=a[i];
			__int128 tmp=1; 
			For(j,l,i-1) tmp=tmp*b[j]%b[i];
			b[i]/=gcd(b[i],tmp);
			ans=b[i]%mo*ans%mo;
		}
		printf("%d\n",ans);
	}
}
int main(){
	int T;
	scanf("%d",&T);
	while (T--) solve();
} 

算法2

然后考虑优化，我们考虑对数组进行分治。

假设我们将数组$a[1\cdots n]$分成$a[1\cdots mid]$和$a[mid+1\cdots n]$。

则我们可以预处理出来$lcm_{i,mid}$和$lcm_{mid+1,i}$。这一部分可以$O(n^2)$预处理

同时我们不难发现，我们可以把这些$lcm看$成两个序列$A,B$，满足:

现在我们需要预处理出所有$A$的前缀积和$B$的前缀积的$lcm$,并转化为$gcd$

此时我们仍然可以将其转成$gcd(\Pi B_i,A_{j})$。

在求完之后我们可以算出$B_i$在这一轮中除去的值。

如果求$gcd$技巧不够高超复杂度会退化为$O(Tn^2logV)$。

如果求$gcd$高超则可以优化至$O(Tn(n+logV))$。

gcd技巧不够高超的做法:

#include<bits/stdc++.h>
#define For(i,j,k) for (int i=(int)(j);i<=(int)(k);i++)
#define Rep(i,j,k) for (int i=(int)(j);i>=(int)(k);i--)
#define ll long long
using namespace std;
const int N=505;
const int mo=1000000007;
int n,Q;
ll a[N],b[N];
int ans[N][N];
ll gcd(ll x,ll y){
	return y?gcd(y,x%y):x;
}
ll mul(ll x,ll y,ll mo){
	y%=mo;
	ll t=x*y-(ll)((long double)x/mo*y+1e-9)*mo;
	return t<mo?t+mo:t;
} 
void solve(int l,int r){
	if (l==r){
		ans[l][l]=a[l]%mo;
		return;
	}
	int mid=(l+r)/2;
	solve(l,mid);
	solve(mid+1,r);
	For(i,mid+1,r){
		b[i]=a[i];
		ll tmp=1;
		For(j,mid+1,i-1) tmp=mul(tmp,b[j],b[i]);
		b[i]/=gcd(b[i],tmp);
	}
	Rep(i,mid,l){
		b[i]=a[i];
		ll tmp=1;
		For(j,i+1,mid) tmp=mul(tmp,b[j],b[i]);
		b[i]/=gcd(b[i],tmp);
	}
	int S1=1;
	Rep(i,mid,l){
		S1=b[i]%mo*S1%mo;
		int S2=S1;
		For(j,mid+1,r){
			ll v=gcd(b[i],b[j]);
			b[i]/=v; b[j]/=v;
			ans[i][j]=S2=b[j]%mo*S2%mo;
		}
	}
}
void solve(){
	scanf("%d%d",&n,&Q);
	For(i,1,n) scanf("%lld",&a[i]);
	solve(1,n);
	For(i,1,Q){
		int l,r;
		scanf("%d%d",&l,&r);
		printf("%d\n",ans[l][r]);
	} 
}
int main(){
	int T;
	scanf("%d",&T);
	while (T--) solve();
} 

code:

#include<bits/stdc++.h>
#define For(i,j,k) for (int i=(int)(j);i<=(int)(k);i++)
#define Rep(i,j,k) for (int i=(int)(j);i>=(int)(k);i--)
#define ll long long
using namespace std;
const int N=505;
const int mo=1000000007;
int n,Q;
ll a[N],b[N],c[N];
int ans[N][N];
ll gcd(ll x,ll y){
	return y?gcd(y,x%y):x;
}
ll mul(ll x,ll y,ll mo){
	y%=mo;
	ll t=x*y-(ll)((long double)x/mo*y+1e-9)*mo;
	return t<mo?t+mo:t;
} 
void solve(int l,int r){
	if (l==r){
		ans[l][l]=a[l]%mo;
		return;
	}
	int mid=(l+r)/2;
	solve(l,mid);
	solve(mid+1,r);
	For(i,mid+1,r){
		b[i]=a[i];
		ll tmp=1;
		For(j,mid+1,i-1) tmp=mul(tmp,b[j],b[i]);
		b[i]/=gcd(b[i],tmp);
	}
	Rep(i,mid,l){
		b[i]=a[i];
		ll tmp=1;
		For(j,i+1,mid) tmp=mul(tmp,b[j],b[i]);
		b[i]/=gcd(b[i],tmp);
	}
	int S1=1;
	Rep(i,mid,l){
		S1=b[i]%mo*S1%mo;
		int S2=S1; c[mid]=1;
		For(j,mid+1,r) c[j]=mul(c[j-1],b[j],b[i]);
		ll G=gcd(c[r],b[i]),rem;
		Rep(j,r-1,mid) if (rem=c[j]%G){
			ll nG=gcd(G,rem);
			b[j+1]/=G/nG; G=nG;
		}
		For(j,mid+1,r)
			ans[i][j]=S2=b[j]%mo*S2%mo;
	}
}
void solve(){
	scanf("%d%d",&n,&Q);
	For(i,1,n) scanf("%lld",&a[i]);
	solve(1,n);
	For(i,1,Q){
		int l,r;
		scanf("%d%d",&l,&r);
		printf("%d\n",ans[l][r]);
	} 
}
int main(){
	int T;
	scanf("%d",&T);
	while (T--) solve();	
}