题目：
参考博客：
算 id 也可以不存下来，因为 \( \left \lfloor \frac{i}{n} \right \rfloor \) 的取值是连续的，当 \( i \leqslant \sqrt{n} \) 时取值就是 \( i \)；
而 \( i > \sqrt{n} \) 时，因为 \( i \) 越大，\( \left \lfloor \frac{i}{n} \right \rfloor \) 越小直到变成 1，所以编号可以直接数到；
注意 int 类型的 \( \sqrt{n} \) 是下取整的，所以判断条件最好写成 \( x > \sqrt{n} \) 而非 \( x \geqslant \sqrt{n} \)；
因为 \( n \) 是 1e10 的，所以各种地方要注意不能爆 long long；
质数的 \( f \) 应该也可以直接筛吧(就直接令所有 \( f[i] = i-1 \))，不过质数和 - 质数个数也很方便。
代码如下：
#include#include #include #include using namespace std;typedef long long ll;int const xn=1e6+5,mod=1e9+7;int m,f[xn],h[xn],pri[xn],cnt,sqr,ps[xn];ll n,w[xn]; bool vis[xn];ll pw(ll a,ll b){a%=mod; b%=(mod-1); ll ret=1; for(;b;b>>=1,a=a*a%mod)if(b&1)ret=ret*a%mod; return ret;}int upt(ll x){ while(x>=mod)x-=mod; while(x<0)x+=mod; return x;}void init(){ for(int i=2;i<=sqr;i++) { if(!vis[i])pri[++cnt]=i,ps[cnt]=upt(ps[cnt-1]+i); for(int j=1;j<=cnt&&(ll)i*pri[j]<=sqr;j++) { vis[i*pri[j]]=1; if(i%pri[j]==0)break; } }}int Id(ll x){ if(x>sqr)return n/x;//>! else return m-x+1;}int S(ll x,int y){ if(x<=1||pri[y]>x)return 0; int k=Id(x); int ret=upt((ll)f[k]-h[k]-(ps[y-1]-y+1)); if(y==1)ret=upt(ret+2); for(int i=y;i<=cnt&&(ll)pri[i]*pri[i]<=x;i++) { ll p0=pri[i],p1=(ll)pri[i]*pri[i];//ll for(int k=1;p1<=x;k++,p0=p1,p1*=pri[i]) ret=upt(ret+(ll)(pri[i]^k)*S(x/p0,i+1)%mod+(pri[i]^(k+1))); } return ret;}int main(){ scanf("%lld",&n); sqr=sqrt(n); int inv2=pw(2,mod-2); init(); for(ll i=1,j;i<=n;i=j+1) { w[++m]=n/i; j=n/(n/i); f[m]=(ll)upt(w[m]+2)*upt(w[m]-1)%mod*inv2%mod;//upt! f[m]=upt(f[m]);//筛质数和 h[m]=upt(w[m]-1);//筛质数个数 } for(int j=1;j<=cnt;j++)//j=1 for(int i=1;i<=m&&w[i]>=(ll)pri[j]*pri[j];i++) { int k=Id(w[i]/pri[j]); f[i]=upt(f[i]-(ll)pri[j]*(f[k]-ps[j-1])%mod); h[i]=upt(h[i]-h[k]+j-1); } printf("%d\n",upt(S(n,1)+1)); return 0;}