【数学】乘性函数

更新于 分类于 ， 阅读次数： 本文字数： 3k 阅读时长 ≈ 3 分钟

乘性函数相关内容，主要欧拉函数相关。

乘性函数

基本定义与性质

  • 算数函数：定义在所有正整数上的函数

  • 乘性函数（积性函数）：算数函数ff ，任意两个互素的正整数 nn 和 mm, 均有 f(mn)=f(m n)= f(m)f(n)f(m) f(n)

  • 完全乘性（完全积性）函数：乘性函数去掉互素的条件。

  • 任意正整数 nn 的素数幂分解 n=p1a1⋅p2a2⋯psasn=p_{1}{ }^{a_{1}} \cdot p_{2}^{a_2} \cdots p_{s}{ }^{a_{s}} ，ff 是乘性函数⇒f(n)=f(p1a1)⋅f(p2a2)⋯f(psas)\Rightarrow f(n)=f\left(p_{1}{ }^{a_{1}}\right) \cdot f\left(p_{2}{ }^{a_{2}}\right) \cdots f\left(p_{s}^{a_s}\right)

  • 积性函数的和还是积性函数

  • 举例：

    • 欧拉函数
    • gcd：gcd⁡(i,m×n)=gcd⁡(i×m)×gcd⁡(i×n),m,n\operatorname{gcd}(i, m \times n)=\operatorname{gcd}(i \times m) \times \operatorname{gcd}(i \times n), m, n 互质

欧拉函数

  • 欧拉函数 φ(n)\varphi(n) ：不超过 nn 且与 nn 互素的正整数的个数，n∈N∗n\in N^*
  • pp 是素数⇔φ(p)=p−1\Leftrightarrow\varphi(p)=p-1
  • pp 是素数，a∈N∗⇒φ(pa)=pa−pa−1a\in N^*\Rightarrow \varphi\left(p^{a}\right)=p^{a}-p^{a-1}
    • 证明：与pap^a 不互素的只有p,2p,3p,⋯ ,pk−1pp,2p,3p,\cdots,p^{k-1}p ，等比求和减去即可
  • 任意正整数 nn 的素数幂分解 n=p1a1⋅p2a2⋯psas⇒φ(n)=n⋅(1−1p1)⋅(1−1p2)⋯(1−1ps)n=p_{1}^{a_{1}} \cdot p_{2}^{a_2} \cdots p_{s}{ }^{a_{s}}\Rightarrow \varphi(n)=n \cdot\left(1-\frac{1}{p_{1}}\right) \cdot\left(1-\frac{1}{p_{2}}\right) \cdots\left(1-\frac{1}{p_{s}}\right)
    • 证明：上一定理还可写成φ(pa)=pa(1−1p)\varphi\left(p^{a}\right)=p^{a}(1-\frac{1}{p}) ，由欧拉函数是积性函数可得上式。
    • 推论：当 nn 为奇数时, 有 φ(2n)=φ(n)\varphi(2 n)=\varphi(n)
  • n>2,n∈N∗⇒φ(n)n>2,n\in N^*\Rightarrow \varphi(n) 是偶数
  • n∈N∗,∑d∣nφ(d)=nn\in N^*,\sum_{d\mid n}\varphi(d)=n
  • 欧拉定理： mm 是一正整数, aa 是一个整数且 (a,m)=1(a, m)=1, 那么 aφ(m)≡a^{\varphi(m)} \equiv 1( mod m)1(\bmod m)
  • xmod  p=0⇒φ(xp)=φ(x)⋅px\mod p=0\Rightarrow \varphi(xp)=\varphi(x)\cdot p ，证明如下：
    • [1,x][1,x] 中与xx 不互质的数yy ，y+xy+x 与xx 仍不互质，y+cx,c≤py+cx,c\leq p 仍与xx 不互质，即[1,x][1,x] 区间中与xx 不互质的数在+cx+cx 后仍不互质。前面素数性质可证[1,x][1,x] 中与xx 互质的数在+cx+cx 后仍互质。所以可得上述结论。

注：以下均来自kuangbin的模板

分解质因数法

上面第四条定理

1
2
3
4
5
6
7
8
int Euler(int n)
{
    getFactors(n); // 前面提过的分解质因数
    int ret = n;
    for (int i = 0; i < fatCnt; i++)
        ret = ret / factor[i][0] * (factor[i][0] - 1);
    return ret;
}

递推法

将φ(i)\varphi(i) 先置为ii ，把kiki 的原始φ\varphi 乘上这个ii 做出的贡献。

过程中，φ\varphi 没有赋值说明是素数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int euler[N];
void getEuler()
{
    memset(euler, 0, sizeof(euler));
    euler[1] = 1;
    for (int i = 2; i < N; i++)
        if (!euler[i])
            for (int j = i; j < N; j += i)
            {
                if (!euler[j])
                    euler[j] = j;
                euler[j] = euler[j] / i * (i - 1);
            }
}

求单个欧拉函数

找素因子，用公式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int euler(int n)
{
    int ans = n;
    for (int i = 2; i * i <= n; i++)
        if (n % i == 0)
        {
            ans -= ans / i;
            while (n % i == 0)
                n /= i;
        }
    if (n > 1)
        ans -= ans / n;
    return ans;
}

线性筛

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
bool check[N + 10];
int phi[N + 10];
int prime[N + 10];
int tot; //素数的个数
void phi_and_prime_table(int N)
{
    memset(check, false, sizeof(check));
    phi[1] = 1;
    tot = 0;
    for (int i = 2; i <= N; i++)
    {
        if (!check[i])
        {
            prime[tot++] = i;
            phi[i] = i - 1;
        }
        for (int j = 0; j < tot; j++)
        {
            if (i * prime[j] > N)
                break;
            check[i * prime[j]] = true;
            if (i % prime[j] == 0)
            {
                phi[i * prime[j]] = phi[i] * prime[j]; // 利用性质
                break;
            }
            else
                phi[i * prime[j]] = phi[i] * (prime[j] - 1); // 积性函数
        }
    }
}