- 求(sumlimits_{i=1}^{n}f(i))其中(f)为积性函数。
- 我们先把烦人的(1)踢掉，接下来都从(2)开始枚举，显然(f(1)=1)。
- 令(P_x)为第(x)个质数，(mn_x)为(x)的最小质因子。
- 设(s_{x,y}=sumlimits_{2le ile x,mn_ige P_y}f(i))
- 设(g_{n,m}=sumlimits_{2le xle n,is[x] or mn_x>P_m}f(x))
- (g_{n,m}=g_{n,m-1}(P_m^2>n))
- (g_{n,m}=g_{n,m-1}-f(P_m) imes [g_{n/P_m,m-1}-sumlimits_{i=1}^{m-1}f(P_i)] (P_m^2le n))
- 实现 : 对第二维滚动。
- 如何处理第一维？
- 回到刚才，求(s_{x,y})。
- (s_{x,y}=sumlimits_{2le ile x,is[i],mn_ige P_y}f(i)+sumlimits_{2le ile x,!is[i],mn_ige P_y}f(i))
- (s_{x,y}=g_{x,infty}-sumlimits_{i=1}^{y-1}f(P_i)+sumlimits_{yle ple sqrt x,is[p],ege 1,p^{e+1}le x}f(P_p^e) imes s_{x/P_p^e,p+1}+sumlimits_{2le ple sqrt x,is[p],ege 2,p^ele x}f(P_p^{e}))
- (s_{x,y}=g_{x,infty}-sumlimits_{i=1}^{y-1}f(P_i)+sumlimits_{yle ple sqrt x,is[p],ege 1,p^{e+1}le x}f(P_p^e) imes s_{x/P_p^e,p+1}+f(P_p^{e+1}))
- 这步需要递归下去，注意到需要的(g)的第一维是(lfloor frac{n}{t} floor)形式的，最多(sqrt n)个，离散化即可。
- 目前不会证，先抄几个定理上来。
- (sumlimits_{pge n,is[p]}=Theta(frac{1}{nln n}))
SP34096 DIVCNTK
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib>
#include <cmath>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define N 200050
int vis[N],cnt,id1[N],id2[N],tot;
ll n,w[N],pri[N];
ull g[N],K;
int S;
int pos(ll x) {return x<=S?id1[x]:id2[n/x];}
void sieve() {
int i,j;
for(i=2;i<N;i++) {
if(!vis[i]) pri[++cnt]=i;
for(j=1;j<=cnt&&i*pri[j]<N;j++) {
vis[i*pri[j]]=1; if(i%pri[j]==0) break;
}
}
}
ull sf(int x) {return (K+1)*x;}
ull f(int x) {return (K+1);}
ull fp(int x,int e) {return K*e+1;}
ull get_s(ll x,int y) {
if(x<=1||pri[y]>x) return 0;
ull ans=g[pos(x)]-sf(y-1);
int i,e;
for(i=y;i<=cnt&&pri[i]*pri[i]<=x;i++) {
ll t=pri[i], tt=t*t;
for(e=1;tt<=x;e++,t=tt,tt*=pri[i]) {
ans+=fp(i,e)*get_s(x/t,i+1)+fp(i,e+1);
}
}return ans;
}
int main() {
sieve();
int T;
scanf("%d",&T);
while(T--) {
scanf("%lld%llu",&n,&K);
S=sqrt(n); tot=0;
ll i,lst,j;
for(i=1;i<=n;i=lst+1) {
lst=n/(n/i); ll t=n/i; w[++tot]=t; g[tot]=t-1;
if(t<=S) id1[t]=tot; else id2[n/t]=tot;
}
for(i=1;pri[i]<=S;i++) {
for(j=1;j<=tot&&w[j]>=pri[i]*pri[i];j++) {
g[j]-=g[pos(w[j]/pri[i])]-(i-1);
}
}
for(i=1;i<=tot;i++) g[i]*=(K+1);
printf("%llu
",get_s(n,1)+1);
for(i=1;i<=tot;i++) w[i]=g[i]=0;
}
}
LOJ#6053. 简单的函数
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
#define N 200050
#define mod 1000000007
ll n,pri[N],w[N],g[N],h[N];
int S,cnt,tot,vis[N],id1[N],id2[N];
int pos(ll x) {return x<=S?id1[x]:id2[n/x];}
ll sum[N];
ll fp(int p,int e) {return (pri[p]^e)%mod;}
ll get_s(ll x,int y) {
if(x<=1||pri[y]>x) return 0;
ll ans=(g[pos(x)]-h[pos(x)]-(sum[y-1]-(y-1)))%mod;
if(y==1) ans=(ans+2)%mod;
int p,e;
for(p=y;p<=cnt&&pri[p]*pri[p]<=x;p++) {
ll t=pri[p],tt=t*t;
for(e=1;tt<=x;e++,t=tt,tt*=pri[p]) {
ans=(ans+fp(p,e)*get_s(x/t,p+1)+fp(p,e+1))%mod;
}
}
return ans;
}
int main() {
ll i,j;
for(i=2;i<N;i++) {
if(!vis[i]) pri[++cnt]=i;
for(j=1;j<=cnt&&i*pri[j]<N;j++) {
vis[i*pri[j]]=1; if(i%pri[j]==0) break;
}
}
for(i=1;i<=cnt;i++) sum[i]=(sum[i-1]+pri[i])%mod;
scanf("%lld",&n);
ll lst;
S=sqrt(n);
for(i=1;i<=n;i=lst+1) {
lst=n/(n/i);
ll t=n/i; w[++tot]=t;
if(t<=S) id1[t]=tot; else id2[n/t]=tot;
g[tot]=(t+2)%(mod<<1)*((t-1)%(mod<<1))/2%mod; h[tot]=t-1;
}
for(i=1;pri[i]<=S;i++) {
for(j=1;j<=tot&&w[j]>=pri[i]*pri[i];j++) {
g[j]=(g[j]-pri[i]*(g[pos(w[j]/pri[i])]-sum[i-1]))%mod;
h[j]=(h[j]-(h[pos(w[j]/pri[i])]-(i-1)))%mod;
}
}
printf("%lld
",(get_s(n,1)+1+mod)%mod);
}
**反正考了我也不会就不写非模板的题了。**