题解 P5655 【基础数论函数练习题】

· · 题解

orz EMT__Mashiro

通过连续使用 \mathrm{lcm}(a,b)=a\cdot \dfrac{b}{\gcd(a,b)}，我们可以将\mathrm{lcm}(a_1,a_2,\cdots ,a_m) 表为若干 b_i 的乘积，即

b_m=a_m,b_i=\frac{a_i}{\gcd(a_i,\prod_{j>i}b_j)}(i<m)

直观的理解就是把 a_i 除掉后面已经计算了的部分. 对应到每个质因子上，相当于对指数先做后缀 \max，然后再做后向的差分，因此只要做后缀的乘积即可算出后缀 \max.（对于下面的部分，这样理解会更加容易）.

考虑在最右边增加一个 a_{m+1} 之后造成的影响，首先有 b_{m+1}'=a_{m+1},然后对于剩下的 b，应该是在原有的 b 上再除掉一个因子. 具体地，有

b_i'=\frac{b_i}{\gcd(b_i,\prod_{j>i}b_j')}

令 c_i=b_i/b_i'，我们有

c_i=\gcd(b_i,a_{m+1}/\prod_{j>i}c_j)

意思是说 a_{m+1} 在前面已经除掉了 \prod_{j>i}c_j，把剩下的部分和 b_i 取一个 \gcd 就得到 c_i.

直接按照这个做，每次令右端点加一，然后算出所有 b_i，复杂度 O(Tn^2\log w)，瓶颈在于 c 的计算.

考虑对每个右端点，不为 1 的 c 只有 O(\log w) 个（因为每次 c\neq 1 都会使得 a_{m+1} 至少除以 2）. 所以现在我们的目标是快速判断这个位置的 c 是否为 1.

令 s_i=\prod_{i\leq j\leq m}b_j'，我们有 \gcd(s_i,a_{m+1})=\prod_{i\leq j\leq m}c_j. 那么如果 \gcd(s_i,a_{m+1})\neq \gcd(s_{i+1},a_{m+1})，我们就知道 c_i\neq 1. 我们断言 \gcd(s_i,a_{m+1})\neq \gcd(s_{i+1},a_{m+1}) 当且仅当 s_{i+1}\bmod \gcd(s_i,a_{m+1})\neq 0，这个可以通过对每个质因子独立考虑来证明. 取模可以通过 (s_{i+1}\bmod a_{m+1})\bmod \gcd(s_i,a_{m+1}) 来完成. 这样我们就只需要进行 O(n\log w) 次求 \gcd，总复杂度 O(Tn(n+\log^2 w))，常数很小.

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=500,mod=1000000007;
int T,n,qn;
long long tmp[N],a[N];
int ans[N][N];
long long gcd(long long a,long long b){return b?gcd(b,a%b):a;}
long long mul(long long a,long long b,long long m)
{
    long long t=a*b-(long long)((long double)a/m*b)*m;
    if(t<0)t+=m;else if(t>=m)t-=m;
    return t;
}
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&n,&qn);
        for(int i=1;i<=n;i++)
        {
            scanf("%lld",a+i);
            tmp[i]=1;for(int j=i-1;j>=1;j--)tmp[j]=mul(tmp[j+1],a[j],a[i]);
            long long t=gcd(tmp[1],a[i]);
            for(int j=1;j<i;j++)
                if(tmp[j+1]%t)
                {
                    long long g=gcd(tmp[j+1],t);
                    a[j]/=t/g,t=g;
                }
            ans[i][i]=a[i]%mod;
            for(int j=i-1;j>=1;j--)ans[j][i]=1ll*ans[j+1][i]*((a[j]%mod))%mod;
        }
        for(int i=1,l,r;i<=qn;i++)
        {
            scanf("%d%d",&l,&r),printf("%d\n",ans[l][r]);
        }
    }
}