补题若干（5）

[https://atcoder.jp/contests/abc412/tasks/abc412_e](素数筛法+枚举）

题意：

设\(A_i\)为\(1,2,3..i\)的\(lcm\)，求\(A_l,A_{l+1}....A_R\) （\(L,R \leq 1e14\)) 的不同数个数

思路：

发现当\(A_{i+1}\) 和 \(A_i\) 不同 当且仅当\(A_{i+1}\)为一个素数幂

所以

1. 将\([1,1e7]\)的素数\(x\)筛出来

2. 确定由\(x\)的幂次方构成的数在区间\([L，R]\)的个数

3. 确定\([L,R]\)区间的素数（一次幂）个数：通过素数筛出

具体的：[\(l/x(上取整） \times x\) ,\(r/x \times\)] 区间每次+\(x\)筛去\(x\)的倍数

const int M=1e7+5;
int vis[M];
int vis2[M];
int vis3[M];
int L,R;
vector<int>p;
void solve(){cin>>L>>R;L++;for(int i=2;i<=1e7;i++){if(!vis[i]){p.pb(i);for(int j=2*i;j<=1e7;j+=i){vis[j]=1;}}}for(int x:p){if(x>R)break;int l = (L+x-1)/x*x, r= R/x*x;if(l==x)l+=x;if(r==x)r-=x;for(int i=l;i<=r;i+=x){vis2[i-L]=1;}int k=x*x;for(;k<=R;k*=x){if(k>=L)vis3[k-L]=1;}}int ans=1;for(int i=0;i<=R-L;i++){ans+=(!vis2[i] || vis3[i]);}cout<<ans;
}