$$ans=\sum_{i=1}^nf(i)$$

1. 若 $p$为质数，则 $f(p)$是一个关于 $p$的多项式，比如 $\mu(p)=-1,\varphi(p)=p-1$.

2. 若 $p$为质数，$e$为正整数，则 $f(p^e)$可以很快求出。（通常是 $O(1)$）

3.$f(n)$为积性函数。

$$\sum_{i=1}^n[i\in Prime]f(i)$$

$$\sum_{i=1}^n[i\in Prime]i^k$$

$$g(n,j)=\sum_{i=1}^n[i\in Prime \ or \ minp(i)>P_j]i^k$$

$$\sum_{i=1}^n[i\in Prime]i^k=g(n,|P|)$$

$$g(n,j)=g(n,j-1)-P_j^k(g(\lfloor\frac{n}{P_j}\rfloor,j-1)-\sum_{i=1}^{j-1}[i\in Prime]i^k)$$

$$\lfloor\frac{\lfloor\frac{a}{b}\rfloor}{c}\rfloor=\lfloor\frac{a}{bc}\rfloor$$

$$S(n,j)=\sum_{i=1}^n[minp(i)>P_j]f(i)$$

$$S(x,y)=g(x,|P|)-\sum_{i=1}^{y}f(P_i)+\sum_{P_k\leq \sqrt{x},k>j}\sum_{e>0,P_k^e\leq x}f(p_k^e)(S(\lfloor\frac{x}{P_k^e}\rfloor,k)+[e>1])$$

$S(n,0)$就是最终答案。

#include<bits/stdc++.h>
#define Rint register LL
using namespace std;
typedef long long LL;
const int N = 1000003, mod = 1e9 + 7, inv2 = 500000004, inv3 = 333333336;
LL n, Sqr, pri[N], tot, pre1[N], pre2[N], ind1[N], ind2[N], g1[N], g2[N], w[N], cnt;
bool notp[N];
inline void init(LL m){
notp[0] = notp[1] = true;
for(Rint i = 2;i <= m;i ++){
if(!notp[i]){
pri[++ tot] = i;
pre1[tot] = (pre1[tot - 1] + i) % mod;
pre2[tot] = (pre2[tot - 1] + i * i) % mod;
}
for(Rint j = 1;j <= tot && i * pri[j] <= m;j ++){
notp[i * pri[j]] = true;
if(!(i % pri[j])) break;
}
}
}
inline LL S(LL x, int y){
if(pri[y] >= x) return 0;
LL k = (x <= Sqr) ? ind1[x] : ind2[n / x];
LL ans = (g2[k] - g1[k] + pre1[y] - pre2[y] + mod + mod) % mod;
for(Rint i = y + 1;i <= tot && pri[i] * pri[i] <= x;i ++){
LL pe = pri[i];
for(Rint e = 1;pe <= x;e ++, pe *= pri[i]){
LL xx = pe % mod;
ans = (ans + xx * (xx - 1) % mod * (S(x / pe, i) + (e > 1))) % mod;
}
}
return ans % mod;
}
int main(){
scanf("%lld", &n);
Sqr = sqrt(n);
init(Sqr);
for(Rint i = 1, last;i <= n;i = last + 1){
last = n / (n / i);
w[++ cnt] = n / i;
LL xx = w[cnt] % mod;
g1[cnt] = (xx * (xx + 1) / 2 + mod - 1) % mod;
g2[cnt] = (xx * (xx + 1) / 2 % mod * (2 * xx + 1) % mod * inv3 % mod + mod - 1) % mod;
if(n / i <= Sqr) ind1[w[cnt]] = cnt;
else ind2[last] = cnt;
}
for(Rint i = 1;i <= tot;i ++)
for(Rint j = 1;j <= cnt && pri[i] * pri[i] <= w[j];j ++){
LL k = (w[j] / pri[i] <= Sqr) ? ind1[w[j] / pri[i]] : ind2[n / (w[j] / pri[i])];
g1[j] -= pri[i] * (g1[k] - pre1[i - 1] + mod) % mod;
g2[j] -= pri[i] * pri[i] % mod * (g2[k] - pre2[i - 1] + mod) % mod;
if(g1[j] < 0) g1[j] += mod;
if(g2[j] < 0) g2[j] += mod;
}
printf("%lld", (S(n, 0) + 1) % mod);
}


## UOJ188#【UR #13】Sanrd

$$S(n,j)=\sum_{i=1}^n[minp(i)>P_j]f(i)$$

$$S(n,j)=\sum_{k>j,P_k\leq \sqrt{n}}\sum_{e>0,P_k^{e+1}\leq n}(S(\lfloor\frac{n}{P_k^e}\rfloor,k)+P_k\sum_{i=P_k}^{\lfloor\frac{n}{P_k}\rfloor}[i\in Prime])$$

#include<bits/stdc++.h>
#define Rint register LL
using namespace std;
typedef long long LL;
const int N = 1000003;
LL Sqr, pri[N], tot, g[N], w[N], id1[N], id2[N], cnt;
bool notp[N];
inline void init(int m){
notp[0] = notp[1] = true;
for(Rint i = 2;i <= m;i ++){
if(!notp[i]) pri[++ tot] = i;
for(Rint j = 1;j <= tot && i * pri[j] <= m;j ++){
notp[i * pri[j]] = true;
if(!(i % pri[j])) break;
}
}
}
inline LL solve(LL n, LL x, int y){
if(x <= 1) return 0;
LL ans = 0;
for(Rint k = y + 1;k <= tot && pri[k] * pri[k] <= x;k ++){
for(Rint pe = pri[k];pe * pri[k] <= x;pe *= pri[k]){
LL kk = (x / pe <= Sqr) ? id1[x / pe] : id2[n / (x / pe)];
ans += solve(n, x / pe, k) + pri[k] * (g[kk] - k + 1);
}
}
return ans;
}
inline LL solve(LL n){
Sqr = sqrt(n);
tot = cnt = 0;
init(Sqr);
for(Rint i = 1, last;i <= n;i = last + 1){
w[++ cnt] = n / i;
last = n / w[cnt];
g[cnt] = w[cnt] - 1;
if(w[cnt] <= Sqr) id1[w[cnt]] = cnt;
else id2[last] = cnt;
}
for(Rint i = 1;i <= tot;i ++)
for(Rint j = 1;j <= cnt && pri[i] * pri[i] <= w[j];j ++){
LL k = (w[j] / pri[i] <= Sqr) ? id1[w[j] / pri[i]] : id2[n / (w[j] / pri[i])];
g[j] -= g[k] - i + 1;
}
return solve(n, n, 0);
}
int main(){
LL l, r;
scanf("%lld%lld", &l, &r);
printf("%lld\n", solve(r) - solve(l - 1));
}


### 6 条评论

#### Remmina · 2020年3月25日 12:16 上午

额，我当时学这玩意的时候似乎是听说这两者是同一个东西，不太记得清了。

#### AThousandMoon · 2019年5月30日 1:10 下午

https://www.cnblogs.com/AThousandMoons/p/10827172.html

#### Remmina · 2019年5月30日 12:57 下午

OvO…
才看懂您的意思，很抱歉耽误这么久，现在我就修改

#### Remmina · 2019年5月30日 1:10 下午

已经提升了 “投稿者” 权限，可以修改和删除自己已发布的文章啦，您可以自行修改了（我没找到您所描述的问题之处）