P3708 koishi的数学题(因数和)
值得学习的点
- 因子和 σ ( n ) = ∑ d ∣ n d \sigma(n)=\sum\limits_{d|n}d σ(n)=d∣n∑d
- x ( m o d y ) = x − ⌊ x y ⌋ × y x\pmod y = x - \lfloor\dfrac{x}{y}\rfloor \times y x(mody)=x−⌊yx⌋×y
f ( x ) = ∑ i = 1 n x ( m o d i ) f(x)=\sum\limits_{i=1}^n x\pmod{i} f(x)=i=1∑nx(modi)，求 f ( 1 ) , f ( 2 ) … , f ( n ) f(1),f(2)\dots,f(n) f(1),f(2)…,f(n)
考虑递推的关系
f ( x ) = ∑ i = 1 n x ( m o d i ) = n x − ∑ i = 1 n ( ⌊ x i ⌋ × i ) f(x)=\sum\limits_{i=1}^n x\pmod {i}=nx-\sum\limits_{i=1}^n (\lfloor\dfrac{x}{i}\rfloor \times i) f(x)=i=1∑nx(modi)=nx−i=1∑n(⌊ix⌋×i)
f ( x ) − f ( x − 1 ) = n − ∑ i = 1 n i ( ⌊ x i ⌋ − ⌊ x − 1 i ⌋ ) f(x)-f(x-1)=n-\sum\limits\limits_{i=1}^n i(\lfloor\dfrac{x}{i}\rfloor-\lfloor\dfrac{x-1}{i}\rfloor ) f(x)−f(x−1)=n−i=1∑ni(⌊ix⌋−⌊ix−1⌋)
当 i ∣ x i|x i∣x时， ( ⌊ x i ⌋ − ⌊ x − 1 i ⌋ ) = 1 (\lfloor\dfrac{x}{i}\rfloor-\lfloor\dfrac{x-1}{i}\rfloor )=1 (⌊ix⌋−⌊ix−1⌋)=1
否则等0。
所以 ∑ i = 1 n i ( ⌊ x i ⌋ − ⌊ x − 1 i ⌋ ) = ∑ d ∣ x x d = σ ( x ) \sum\limits\limits_{i=1}^ni(\lfloor\dfrac{x}{i}\rfloor-\lfloor\dfrac{x-1}{i}\rfloor )=\sum\limits_{d|x}^x d=\sigma(x) i=1∑ni(⌊ix⌋−⌊ix−1⌋)=d∣x∑xd=σ(x)
f ( x ) − f ( x − 1 ) = n − σ ( x ) f(x)-f(x-1)=n-\sigma(x) f(x)−f(x−1)=n−σ(x)
预处理 σ ( i ) \sigma(i) σ(i)，然后 O ( n ) O(n) O(n)递推。
预处理 σ ( i ) \sigma(i) σ(i)的两种方法：
- 每个因数的对哪些数有贡献 O ( n l o g n ) O(nlogn) O(nlogn)
- 线性筛 O ( n ) O(n) O(n)
//暴力筛O(nlogn)
ll f[N],s;
int n;
void init(int n){
for(int i=1;i<=n;i++)
for(int j=i;j<=n;j+=i) f[j]+=i;
}
//线筛O(n)
ll f[N],s,g[N];
int p[N],cnt,vis[N];
int n;
void init(int n){
vis[0]=vis[1]=1;
f[1]=1;
for(int i=2;i<=n;i++){
if(!vis[i]) p[++cnt]=i,f[i]=g[i]=i+1;
for(int j=1;j<=cnt&&i*p[j]<=n;j++){
vis[i*p[j]]=1;
if(i%p[j]==0){
g[i*p[j]]=g[i]*p[j]+1;
f[i*p[j]]=f[i]/g[i]*g[i*p[j]];
break;
}
f[i*p[j]]=f[i]*f[p[j]];
g[i*p[j]]=g[p[j]];
}
}
}
因数和线筛的证明
自己来证明下 O ( n ) O(n) O(n)的线筛：
前置知识：
- 欧拉筛
- 约数定理： n = p 1 k 1 p 2 k 2 … p m k m = ( 1 + p 1 + p 1 2 + p 1 3 ⋯ + p 1 k 1 ) ( 1 + p 2 + p 2 2 + ⋯ + p 2 k 2 ) . . . ( 1 + p m + p m 2 + ⋯ + p m k m ) n=p_1^{k_1}p_2^{k_2}\dots p_{m}^{k_m}=(1+p_{1}+p_1^2+p_1^3\dots+p_1^{k_1})(1+p_2+p_2^2+\dots+p_2^{k_2})...(1+p_m+p_m^{2}+\dots +p_m^{k_m}) n=p1k1p2k2…pmkm=(1+p1+p12+p13⋯+p1k1)(1+p2+p22+⋯+p2k2)...(1+pm+pm2+⋯+pmkm)
令 f ( n ) = σ ( n ) = ∑ d ∣ n n d f(n)=\sigma(n)=\sum\limits_{d|n}^n d f(n)=σ(n)=d∣n∑nd
g ( n ) g(n) g(n)中通过素数定理化简后得到的最小那一组素因子项。
也就是 g ( n ) = ( 1 + p 1 + p 1 2 + p 1 3 ⋯ + p 1 k 1 ) g(n)=(1+p_{1}+p_1^2+p_1^3\dots+p_1^{k_1}) g(n)=(1+p1+p12+p13⋯+p1k1)
这个用处后面再说。
分情况讨论：
-
i i i是质数，则 f ( i ) = g ( i ) = i + 1 f(i)=g(i)=i+1 f(i)=g(i)=i+1，这个比较显然。
-
i i i不是质数，又分两种情况
pos1
i ( m o d p j ) = 0 i\pmod{ p_j}=0 i(modpj)=0， p j p_j pj是当前用来筛的质数。因为欧拉筛使用最小的质数筛的，所以 p j p_j pj一定是 i i i的最小质因子。所以 g ( i × p j ) = g ( i ) × p j + 1 = ( 1 + p j + p j 2 + ⋯ + p j k 1 ) × p j + 1 = ( 1 + p j + p j 2 + ⋯ + p j k 1 + 1 ) g(i\times p_j)=g(i)\times p_j+1=(1+p_j+p_j^2+\dots+p_j^{k_1})\times p_j+1=(1+p_j+p_j^2+\dots+p_j^{k_1+1}) g(i×pj)=g(i)×pj+1=(1+pj+pj2+⋯+pjk1)×pj+1=(1+pj+pj2+⋯+pjk1+1)
f ( i × p j ) = f ( i ) g ( i ) × g ( i × p j ) f(i\times p_j)=\dfrac{f(i)}{g(i)}\times g(i\times p_j) f(i×pj)=g(i)f(i)×g(i×pj)
pos2
i ( m o d p j ) ≠ 0 i\pmod{p_j}\neq 0 i(modpj)=0，则 g ( i × p j ) = g ( p j ) g(i\times p_j)=g(p_j) g(i×pj)=g(pj)， f ( i × p j ) = f ( i ) × f ( p j ) f(i\times p_j)=f(i)\times f(p_j) f(i×pj)=f(i)×f(pj)，这个根据积性函数的性质或者定义都可以得到。
因此可以实现 O ( n ) O(n) O(n) 求出 σ ( i ) \sigma(i) σ(i)了。