A
B
记 \(f^k(x)\) 为 \(f(x)\) 嵌套 \(k\) 次的结果。当 \(k\le 0\) 时，另外定义 \(f^k(x)=x\).
给出 \(B\) 和 \(T\) 组 \(L,R\)，求
\[\sum_{i=L}^{R}\varphi^{\max_{j=1}^{i}\varphi(j)-B}(i)
\]
\(1\le T\le 10^5\)，\(1\le L\le R\le 10^9\)，\(0\le B\le 10^9\).
唯一能做的一个题。
最大值的式子其实就是最接近 \(i\) 的质数 \(j-1,j\in P\).
首先 \(x\leftarrow \varphi(x)\) 这个操作的层数是严格 \(\le \lfloor\log p\rfloor+1\) 的。
设一个阈值 \(M\)，由于质数密度可以暴力地把所有数分为 \([1,B]\)，\([B+1,B+M]\)，\((B+M,N]\) 三段，左边的 \(f(i)=i\)，中间的预处理出来，右边的 \(f(i)=1\)。（中间的数比较少）
然后就做完了。
点击查看代码
#include<bits/stdc++.h>
#pragma GCC optimize(3)
#define ll long long
#define N 1000000000
#define M 1000
using namespace std;
int read(){
int x=0,w=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}
while(isdigit(ch))x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
return x*w;
}
int B;
map<int,int>phi;
bool isprime(int n){
if(n<2)return false;
if(n==2)return true;
for(int i=2;i*i<=n;i++)
if(n%i==0)return false;
return true;
}
ll f[M+5];int g[M+5];
int getphi(int n){
if(phi[n])return phi[n];
int ret=n,tp=n;
for(int i=2;i*i<=n;i++){
if(n%i==0){
ret-=ret/i;
while(n%i==0)n/=i;
}
}
if(n>1)ret-=ret/n;
return phi[tp]=ret;
}
void init(){
for(int i=B+1;i<=min(B+M,N);i++){
if(isprime(i))g[i-B]=i-1-B;
else g[i-B]=g[i-B-1];
}
for(int i=B+1;i<=min(B+M,N);i++){
f[i-B]=i;
for(;f[i-B]!=1&&g[i-B];g[i-B]--)
f[i-B]=getphi(f[i-B]);
f[i-B]+=f[i-B-1];
}
}
int main(){
freopen("b.in","r",stdin);
freopen("b.out","w",stdout);
int T=read();B=read();
init();
int L,R;ll ans;
while(T--){
L=read(),R=read();
if(R<=B){
ans=1ll*R*(R+1)/2-1ll*L*(L-1)/2;
printf("%lld\n",ans);
continue;
}
if(L>B+M){
printf("%d\n",R-L+1);
continue;
}
ans=0;
if(L<=B)ans+=1ll*B*(B+1)/2-1ll*L*(L-1)/2;
if(R>B+M)ans+=R-B-M;
ans+=f[min(M,R-B)]-f[max(0,L-1-B)];
printf("%lld\n",ans);
}
return 0;
}