P5655 基础数论函数练习题 解题报告

解题报告

---

P5655 基础数论函数练习题解题报告：

题意

给定一个长度为 $n$ 的序列，$q$ 次询问一个区间的 $\text{lcm}$，$T$ 组数据。

$1\leqslant n,q,T\leqslant 300$。

分析

$T,n$ 这么小显然提示我们预处理所有答案，设 $f_{l,r}$ 表示区间 $[l,r]$ 的 $\text{lcm}$。

考虑分治，当前分治到区间 $[l,r]$，中点为 $mid$，那么我们要处理所有越过中点的区间的 $\text{lcm}$。

发现我们可以根据 $a$ 生成一个序列 $b$，满足 $b_i\mid a_i,f_{mid,k}=\prod_{i=mid}^kb_i,f_{k,mid}=\prod_{i=k}^{mid}b_i$。

这个东西可以直接递推（很显然吧）

$$b_i=\begin{cases}\frac{a_i}{\gcd(a_i,\prod_{j=i+1}^{mid}b_j)} &i<mid\\\frac{a_i}{\gcd(a_i,\prod_{j=mid}^{i-1}b_j)}&i>mid\end{cases}$$

然后考虑经过 $mid$ 的区间的答案，我们固定左端点为 $i$，设当前右端点为 $j$，我们发现每次移动左端点的时候会让某些 $j$ 失去某些质因子，也就是说我们可以在移动 $i$ 的时候动态更新 $b_j$ 的值。

具体，我们发现可以先求出 $\gcd(b_i,\prod_{j=mid+1}^r b_j)$，然后我们找这个 $\gcd$ 每一个因子是哪个位置贡献的，删去这个因子就好了，这样我们的时间复杂度就是 $O(Tn^2)$ 了。

有一个小细节，乘法需要使用玄学的快速乘，我也不知道这为什么是对的。

代码

#include<stdio.h>
#define int long long
const int maxn=305,mod=1000000007;
int T,n,q;
int ans[maxn][maxn],a[maxn],b[maxn],c[maxn];
int gcd(int a,int b){
    return b==0? a:gcd(b,a%b);
}
inline int getmul(int a,int b,int mod){
    a%=mod,b%=mod;
    long long res=a*b-(int)((long double)a/mod*b)*mod;
    return res<0? res+mod:res;
}
void solve(int l,int r){
    if(l==r){
        ans[l][l]=a[l]%mod;
        return; 
    }
    int mid=(l+r)>>1;
    solve(l,mid),solve(mid+1,r);
    for(int i=mid;i>=l;i--){
        int prod=1;
        for(int j=i+1;j<=mid;j++)
            prod=getmul(prod,b[j],a[i]);
        b[i]=a[i]/gcd(a[i],prod);
    }
    for(int i=mid+1;i<=r;i++){
        int prod=1;
        for(int j=i-1;j>mid;j--)
            prod=getmul(prod,b[j],a[i]);
        b[i]=a[i]/gcd(a[i],prod);
    }
    int prod=1;
    for(int i=mid;i>=l;i--){
        prod=b[i]%mod*prod%mod;
        c[mid]=1;
        for(int j=mid+1;j<=r;j++)
            c[j]=getmul(c[j-1],b[j],b[i]);
        int g=gcd(c[r],b[i]);
        for(int j=r;j>mid;j--)
            if(c[j-1]%g){
                int tmp=gcd(g,c[j-1]);
                b[j]/=(g/tmp),g=tmp;
            }
        int PROD=prod;
        for(int j=mid+1;j<=r;j++){
            PROD=b[j]%mod*PROD%mod;
            ans[i][j]=PROD;
        }
    }
}
signed main(){
    scanf("%lld",&T);
    while(T--){
        scanf("%lld%lld",&n,&q);
        for(int i=1;i<=n;i++)
            scanf("%lld",&a[i]);
        solve(1,n);
        while(q--){
            int x,y;
            scanf("%lld%lld",&x,&y);
            printf("%lld\n",ans[x][y]);
        }
    }
    return 0;
}