【2】ABC412E - LCM Sequence 解题报告【数学】

· · 题解

题意：给你一个区间 [l,r]，设 a_i 是 1 到 i 的最小公倍数的值。问当 l\leq i\leq r 时出现过多少个不同的 a_i，数据范围满足 1\leq l,r\leq 10^{14},r-l\leq 10^7。

这题我主要通过对最小公倍数的变动次数，来统计答案。

对原有质因数范围的判定

对于这个题，我们自然想到对 a_l 分解质因数。注意到 > 10^7 的质因子需要再出现一次的话就需要一个 >10^{14} 的数，所以我们考虑所有质因子只考虑 \leq 10^7 的即可。

情况：出现原有的质因子

我们发现对于一个可能出现新次数的质因数 p，设原先出现次数为 e，那么我们要判断是否出现了 p^e，p^{e+1}，p^{e+2} 等更多的出现次数。我们注意到 e\ge 2，那么枚举更多可能出现个数的复杂度就将会是 \mathcal O(\log_{e}r)。这是可以接受的。

具体的，我们枚举所有可能的数 p，暴力计算是否 p^x\leq r，其中 x 是一个从 e+1 开始不断往上枚举的数。当 p^x 有一个倍数是在 [l,r] 之间的，那么我们就证明了会因为 p^x 导致数的变化，统计出这导致的变动次数。

情况：出现新的质因子

这个情况相当于 [l,r] 之中出现了质数，那么我们要证明不会出现不存在的质因子。

证明：假设出现一个 10^7<p<l，且 p^2\leq r 的质因子，落在 [l,r] 里。那么我们就会发现，出现了 10^{14}\leq r，不可能出现。

所以 p^2>r，所以 l\leq p\leq r 就是一个质数。那么我们就可以想一个办法处理出 l<p\leq r 的质数。注意不能取到 l，因为这个质数不会造成修改。我们想如何统计这个质数。注意我们有一个埃筛，是 \mathcal O(n\log \log n) 的（证明略），我们考虑将 r-l\leq 10^7 这个条件应用。我们发现因为我们可以求出 \leq 10^7 的所有质数，并且其他的质数 10^7<p 是不能用于筛去 [l,r] 内的质数，所以我们可以只用 2\leq p\leq 10^7 的质数去筛出 [l,r] 内的质数。这很有用，我们可以精确筛去 [l,r] 内的合数，并且复杂度也是可以接受的。

总方法

那么到现在，我们统计了：

这包含了所有的答案，注意出现数量要加上初始数量的 1。这样，我们就用不超过 \mathcal O(n\log n) 的复杂度解决问题，这里 n=r-l。我们应当可以在要求的时限内通过。

这里给出我的出错位置：

  1. 注意 [l,r] 中取 p 倍数需要用好三目运算符，代码里的比较乱，大致就是 l 的下区间要向上取整，r 的上区间要向下取整，可以结合自己的写法。
  2. 注意极限可能会出现一个 10^7\times 10^{14} 的乘法，需要开好朋友 __int128。
  3. 再次强调枚举新质数范围不要包括 l 范围，原因见上文。不然你会因为只错一个点破防。
  4. 注意到问的是出现数量，这个数就是我们求出来的变动数量加上 1。
  5. 还有一个，我们不要乱用 map，可以加上一个偏移值 -l 来用数组来存储，不然直接给你卡超时高达 10000+ 毫秒。

代码如下：

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e7+10;
int l,r,ans;
int gg(int x,int y){
    if(!y)
        return x;
    return gg(y,x%y);
}
vector<int>Prime;
bool is[N];
int hh[N];
vector<pair<int,int> >l_lcm;
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>l>>r;
    memset(is,1,sizeof(is));
    is[0]=is[1]=0;
    for(int i=2;i<=(int)1e7;i++)if(is[i]){
        Prime.push_back(i);
        for(int j=i+i;j<=(int)1e7;j+=i)is[j]=0;
        for(int j=(l%i?(l/i+1)*i:l);j<=(r/i)*i;j+=i)if(j!=i)
            hh[j-l]=1;
    }
    for(auto p:Prime){
        if(p*p>r)
            break;
        int e=0;
        __int128 mul=1;
        while(mul*p<=l){
            ++e;
            mul*=p;
        }
        l_lcm.push_back({p,e});
    }
    for(auto v:l_lcm){
        int val=1;
        if(v.second==0)
            val*=v.first;
        for(int i=1;i<=v.second;i++)
            val=val*v.first;
        __int128 mul=val;
        while(mul*v.first<=r){
            val=val*v.first;
            int ll=(l%val?(l/val+1):l/val),rr=r/val;
            ans+=bool(rr-ll+1);
            mul*=v.first;
        }
    }
    for(int j=l;j<=r;j++)
        if(!hh[j-l]&&j>l)++ans;
    cout<<ans+1;
    return 0;
}