【洛谷P5655】基础数论函数练习题 | Mrsrz's blog

数论+珂学卡常

题目大意：

多组数据，每组给定 $n$ 个数，多次询问一个区间内的最小公倍数。

题解：

我们对质因子 $p^k$ 的贡献进行考虑。我们只在 $p^k$ 最后出现的地方计算 $p$ 的贡献。

意思是说，我们每新插入一个数，其包含 $p,p^2,\dots,p^k$，那么我们令 $p^1\sim p^k$ 的贡献都计算在最后一个位置上，之前再出现 $p$ 的话，就表示 $p^{k+1},p^{k+2},\dots$，这样保证任意一个以当前的数结尾的区间的乘积恰好是最小公倍数，没有重复。

例如：数列 $p^5,\dots,p^3,\dots,p^2$ 的实际情况是 $p^2,1,1,\dots,p,1,1,\dots,p^2$。

本题的值域范围较大，对每个数分解质因数是不可行的。我们需要想办法整体计算贡献。

我们新加入一个 $a$ 的时候，和前面每个数考虑，依次取 $\gcd$，其值就是 $a$ 中和它重复的部分。我们把重复的部分在当前数中除掉，同时在 $a$ 中除掉（因为之前的数的贡献独立，除掉的部分不能和之前的再考虑），然后继续向前考虑（最终插入的还是原来的 $a$）。

这样插入后，以当前结点为结尾的区间的最小公倍数，就是当前存的每个数的乘积。

时间复杂度 $O(T(q+n^2\log a))$，需要在求 $\gcd$ 的时候加上珂学优化才可以通过。

Code：

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include<cstdio>
#include<cctype>
#include<cstdlib>
#include<algorithm>
using namespace std;
typedef long long LL;
const int N=305,md=1e9+7;
char buf[(int)1e8],*ss=buf;
inline int init(){buf[fread(buf,1,(int)1e8-1,stdin)]='\n';fclose(stdin);return 0;}
const int __START__=init();
inline LL readint(){
    LL d=0;
    while(*ss<'0')++ss;
    while(*ss>='0')d=d*10+(*ss++^'0');
    return d;
}
int n,T,q;
LL a[N];
int ans[N][N];
inline LL gcd(LL a, LL b){
    if(!a||!b)return a|b;
    register int t=__builtin_ctzll(a|b);
    a>>=__builtin_ctzll(a);
    do{
        b>>=__builtin_ctzll(b) ;
        if(a>b){LL t=b;b=a,a=t;}
        b-=a;
    }while(b);
    return a<<t;
}
int main(){
    for(T=readint();T--;){
        n=readint(),q=readint();
        for(register int r=1;r<=n;++r){
            a[r]=readint();
            LL x=a[r];
            int*Ans=ans[r];
            Ans[r]=x%md;
            for(register int i=r-1;i;--i){
                LL k=x==1?1:gcd(x,a[i]);
                a[i]/=k,x/=k;
                Ans[i]=Ans[i+1]*(LL)(a[i]%md)%md;
            }
        }
        while(q--){
            int l=readint(),r=readint();
            printf("%d\n",ans[r][l]);
        }
    }
    return 0;
}