T6题解

· · 题解

算法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，满足:

\Pi_{j=mid}^{j \geq i}A_i=lcm_{i,mid} \Pi_{j=mid+1}^{j \leq i}B_i=lcm_{mid+1,r}

现在我们需要预处理出所有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();    
}