积性函数
引入：
我们在线性筛质数的时候使用的方法是这样的
void GetPrime(int n){
memset(isPrime, 1, sizeof(isPrime));
isPrime[1] = 0;//1不是素数
for(int i = 2; i <= n; i++){
if(isPrime[i])
Prime[++cnt] = i;
for(int j = 1; j <= cnt && i*Prime[j] <= n; j++) {
isPrime[i*Prime[j]] = 0;
if(i % Prime[j] == 0)
break;
}
}
}
在这个程序里面我们保证一些东西：
1. \(i \mod Prime[j] == 0\) 时候 \(Prime[j]\) 一定是 \(i\) 的最小质因子
从小到大枚举 \(Prime[j]\) 这显而易见
2.$i \times Prime[j] $中 \(Prime[j]\) 一定是最小质因子
设 \(x=i\times Prime[j]\)
如果有更小的质因子 \(p\) ，那么一定满足 \(i \mod p=0\) 会在前面直接判断跳出循环
3. \(x\) 一定被筛一次并且被他的最小质因子筛
积性函数：
定义：一个数是积性函数当且仅当：
\[f(nm) = f(n)f(m)~~~~(\gcd(m, n) = 1) \]而在积性函数中，经常使用到以下几个重要的积性函数（容易证明它们都是积性的）：
• \(\tau(n)\) 表示正整数 \(n\) 的正因子个数。
• \(\sigma(n)\) 表示正整数 \(n\) 的正因子和。
• \(\mu(n)\) 表示正整数 \(n\) 的 Mobius 函数值。
• \(\varphi(n)\) 表示正整数 \(n\) 的欧拉函数值，即 [1, n] 中与 n 互质的数的个数。
积性函数一般搭配线性筛用
我在这里以 \(\tau(n)\) 为例子
当
\[f(nm) = f(n)f(m)~~~~(\gcd(m, n) = 1) \]可以直接相乘
当\(i \mod Prime[j] == 0\)
我们设 \(x = i,y=prime[j]\)
那么一定有
\[x=k\times y^m \]那么可以表示为
\[x\times y=k\times y^{m+1} \]这样 \(k\) 和 \(y^{m+1}\) 一定互质，可以直接相乘
但假如 \(i = 16,Prime[j]=2\)
那么 \(k=1,y^{m+1}=32\)
我们并没有算出 \(32\) 的函数值，怎么办呢？
我们可以发现 \(y^{m+1}\) 的特性，他的因子一定是
\[y^0,y^1,y^2...y^{m+1} \]函数值就直接等于 \(m+2\)
这样就有了以下代码
void pre(){
a[1] = 1;
for(int i = 2;i <= N; ++i){
isP[i] = 1;
}
for(int i = 2;i <= N; ++i){
if(isP[i] == 1){
prime[++tot] = i;
a[i] = 2;//如果是质数一定有两个因子
}
for(int j = 1;j <= tot && prime[j] * i <= N - 10; ++j){
isP[prime[j] * i] = 0;
if(i % prime[j] == 0){
int add = 0,sum = 0,x = i,y(prime[j]);
while(x % y == 0){
x = x / y;
add++;
}
a[prime[j] * i] = a[x] * (2 + add);
break;
}
a[prime[j] * i] = a[prime[j]] * a[i];
}
}
}
但时间复杂度变成了 \(O(n\log n)\) ，如何优化？
我们记录 \(add_i\) 表示 \(i\) 的最小质因子，就可以用空间换时间：
具体代码实现如下
void pre(){
a[1] = 1;
for(int i = 2;i <= N; ++i){
isP[i] = 1;
}
for(int i = 2;i <= N; ++i){
if(isP[i] == 1){
prime[++tot] = i;
a[i] = 2;//如果是质数一定有两个因子
add[i] = 1;//注意
}
for(int j = 1;j <= tot && prime[j] * i <= N - 10; ++j){
isP[prime[j] * i] = 0;
if(i % prime[j] == 0){
int x = i,y(prime[j]);
add[i * prime[j]] = add[i] + 1;//注意
a[prime[j] * i] = a[x/(add[i])] * (1 + add[i]);//注意
break;
}
a[prime[j] * i] = a[prime[j]] * a[i];
add[i * prime[j]] = 1;//注意
}
}
}