LOJ

分析

注意到

$$ f(p)=\begin{cases}3,&p=2\\p-1,&p\neq 2\end{cases} $$

如果能让这个 $f(2)$ 的值变为 $1$,这个题将变成 Min_25 板子题,可是变不得。所以我们尝试令 $f(p)=p-1$ 然后跑 Min_25 筛,考虑会对答案产生什么影响。

考虑 Min_25 筛第二步的那个式子中质数的贡献

$$ S(n,j)=g(n,|P|)-\sum_{i=1}^{j-1}f(p_i)+\cdots $$

如果令 $f(2)=1$,那么当 $j=1$ 时这部分贡献会比正确的值少 $2$,于是此时直接把算出来的结果加上 $2$ 即可。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <bits/stdc++.h>
#define re register
using namespace std;
typedef long long ll;

inline ll read() {
    ll X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=200000+10;
const int mod=1e9+7,inv2=500000004;

ll n; int s;

int p[N],v[N],cnt=0;
inline void sieve(int n) {
    for (re int i=2;i<=n;++i) {
        if (!v[i]) p[++cnt]=i;
        for (re int j=1;j<=cnt&&i*p[j]<=n;++j) {
            v[i*p[j]]=1; if (i%p[j]==0) break;
        }
    }
}

ll w[N]; int id1[N],id2[N],top=0;
int g0[N],g1[N],gs1[N];

inline int S(ll x,int j) {
    if (x<=1||p[j]>x) return 0;
    int k=x<=s?id1[x]:id2[n/x];
    int res=((1ll*g1[k]-g0[k]-gs1[j-1]+(j-1))%mod+mod)%mod;
    if (j==1) res+=2;
    for (re int i=j;i<=cnt&&1ll*p[i]*p[i]<=x;++i) {
        ll p1=p[i],p2=1ll*p[i]*p[i];
        for (re int e=1;p2<=x;++e,p1=p2,p2*=p[i])
            res=(res+1ll*S(x/p1,i+1)*(p[i]^e)%mod+(p[i]^(e+1))%mod)%mod;
    }
    return res;
}

int main() {
    n=read(),s=sqrt(n); sieve(s);
    for (re int i=1;i<=cnt;++i) gs1[i]=(gs1[i-1]+p[i])%mod;
    for (re ll l=1,r;l<=n;l=r+1) {
        r=n/(n/l); w[++top]=n/l;
        n/l<=s?id1[n/l]=top:id2[n/(n/l)]=top;
        int x=(n/l)%mod;
        g0[top]=(x-1+mod)%mod;
        g1[top]=(1ll*x*(x+1)%mod*inv2%mod-1+mod)%mod;
    }
    for (re int i=1;i<=cnt;++i)
        for (re int j=1;j<=top&&1ll*p[i]*p[i]<=w[j];++j) {
            ll x=w[j]/p[i]; int k=x<=s?id1[x]:id2[n/x];
            g0[j]=(g0[j]-(g0[k]-(i-1)+mod)%mod+mod)%mod;
            g1[j]=(g1[j]-1ll*p[i]*(g1[k]-gs1[i-1]+mod)%mod+mod)%mod;
        }
    printf("%d\n",(S(n,1)+1)%mod);
    return 0;
}
最后修改:2020 年 02 月 13 日 05 : 26 PM