预处理g时，有个式子是\(g(pri_j-1,j-1)\)，也就是前\(j-1\)个质数的前缀和。所以预处理质数时同时预处理一下前缀和。
code /* * @Author: wxyww * @Date: 2019-12-22 17:42:00 * @Last Modified time: 2019-12-24 21:58:42 */ #include<cstdio> #include<iostream> #include<cstdlib> #include<cstring> #include<cmath> #include<algorithm> #include<queue> #include<vector> #include<ctime> using namespace std; typedef long long ll; const int N = 2000010,mod = 1e9 + 7; ll read() { ll x = 0,f = 1;char c = getchar(); while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar(); } while(c >= '0' && c <= '9') { x = x * 10 + c - '0'; c = getchar(); } return x * f; } int tot; ll n,m,w[N],pri[N],sum[N],js,vis[N],g[N],h[N]; void pre() {//筛出质数 for(int i = 2;i <= m;++i) { if(!vis[i]) { pri[++js] = i; sum[js] = sum[js - 1] + i; sum[js] %= mod; } for(int j = 1;j <= js && i * pri[j] <= m;++j) { vis[pri[j] * i] = 1; if(i % pri[j] == 0) break; } } } int id1[N],id2[N]; ll S(ll now,int x) { if(now <= 1 || pri[x] > now) return 0; // printf("%lld %d\n",now,x); int k; if(now <= m) k = id1[now]; else k = id2[n / now]; ll ret = (g[k] - h[k] - sum[x - 1] + x - 1) % mod; if(x == 1) ret += 2;//f(2)当作1计算，实际上f(2)=3 for(int k = x;k <= js && pri[k] * pri[k] <= now;++k) { ll p = pri[k]; for(int e = 1;p * pri[k] <= now;p = p * pri[k],++e) { ret += (pri[k] ^ e) * S(now / p,k + 1) % mod + (pri[k] ^ (e + 1)); ret %= mod; } } return ret; } int main() { // freopen("1.in","w",stdout); n = read(); m = sqrt(n); pre(); // puts("!!!"); for(ll l = 1,r;l <= n;l = r + 1) { r = n / (n / l); ll tmp = n / l; w[++tot] = tmp; if(tmp <= m) id1[tmp] = tot;//数组不够大，通过id1和id2来映射到sqrt(n)以内 else id2[n / tmp] = tot; g[tot] = (tmp + 2) % mod * ((tmp - 1) % mod) % mod; if(g[tot] & 1) g[tot] += mod; g[tot] /= 2; // g[tot] %= mod; h[tot] = tmp - 1; } // for(int i = 1;i <= tot;++i) printf("%lld ",g[i]); for(int j = 1;j <= js;++j) { for(int i = 1;i <= tot && pri[j] * pri[j] <= w[i];++i) {//枚举顺序不能颠倒 ll tmp = w[i] / pri[j]; int k; if(tmp <= m) k = id1[tmp]; else k = id2[n / tmp]; g[i] -= pri[j] * (g[k] - sum[j - 1]) % mod;//枚举顺序不能颠倒的原因 g[i] %= mod; h[i] -= (h[k] - (j - 1)); h[i] %= mod; } } // cout<<g[tot - 2]<<endl; cout<<(S(n,1) + 1 + mod) % mod;//单独把1算上 return 0; }