数论基础

整除

\(\lceil\dfrac{n}{m}\rceil=\lfloor\dfrac{n+m-1}{m}\rfloor=\lfloor\dfrac{n-1}{m}\rfloor+1\)

\(\lfloor\dfrac{n}{m}\rfloor=\dfrac{n}{m}-n\mod m\)

最大公因数

• 已知 \(a>1,m>0,n>0\)，则 \(\gcd(a^m-1,a^n-1)=a^{\gcd(m,n)}-1\)

• 已知 \(a>b,\gcd(a,b)=1\)，则 \(\gcd(a^m-b^m,a^n-b^n)=a^{\gcd(m,n)}-b^{\gcd(m,n)}\)

裴蜀定理

• 若 \(a,b\) 是不全为 \(0\) 的整数，则存在整数 \(x,y\) 使 \(ax+by=\gcd(a,b)\) 成立

• 若 \(\gcd(a,b)=1\) 则 \(C=ab-a-b\) 为 \(ax+by\) \((x,y≥0)\) 所表示不了的最大整数

• 在上个条件下 对任意整数 \(n\)，\(n\) 与 \(C-n\) 有且仅有一个可以被表示

费马小定理

• 若 \(p\) 为素数，且 \(\gcd(a,p)=1\)，则 \(a^{p-1}\equiv1\pmod p\)

威尔逊定理

• 对于素数 \(p\) 有 \((p-1)!\equiv-1\pmod p\)

推广

对于素数 \(p\) 和正整数 \(q\) 有 \((p^q!)_p\equiv\pm1\pmod {p^q}\)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

int factmod(int n, int p) {
    vector<int> f(p);
    f[0] = 1;
    for (int i = 1 ; i < p ; i++) {
        f[i] = f[i - 1] * i % p;
    }
    int res = 1;
    while (n > 1) {
        if ((n / p) & 1) res = p - res;
        res = res * f[n % p] % p;
        n /= p;
    }
    return res;
}

1
2
3
4
5
6
7
8

int multiplicity_factorial(int n, int p) {
  int count = 0;
  do {
    n /= p;
    count += n;
  } while (n);
  return count;
}

加性函数

若函数 \(f(n)\) 满足 \(f(1)=0\)，且 \(\gcd(x,y)=1\)，\(f(x*y)=f(x)+f(y)\)，则 \(f(n)\) 为加性函数。

若函数 \(f(n)\) 满足 \(f(1)=0\)，且 \(f(x*y)=f(x)+f(y)\)，则 \(f(n)\) 为完全加性函数

加性函数相加还是加性函数

常见的加性函数

\(\Omega(n)=\sum_{p\in prime}\sum_{p^k|n}1\) (完全加性)

互异质因子数 \(\omega(n)=\sum_{p\in prime}[p|n]\) (加性)

\(a_0(n)=\sum_{p\in prime}\sum_{p^k|n}p\) (完全加性)

互异质因子和 \(a_1(n)=\sum_{p\in prime}([p|n]*p)\) (加性)

积性函数

若函数 \(f(n)\) 满足 \(f(1)=1\)，且 \(\gcd(x,y)=1\)，\(f(x*y)=f(x)*f(y)\)，则 \(f(n)\) 为积性函数。

若函数 \(f(n)\) 满足 \(f(1)=1\)，且 \(f(x*y)=f(x)*f(y)\)，则 \(f(n)\) 为完全积性函数

积性函数相乘还是积性函数

若 \(f(x)\) 和 \(g(x)\) 均为积性函数，则以下函数也为积性函数：

设 \(x=\prod p_i^{k_i}\)，若 \(f(x)\) 为积性函数，则 \(f(x)=\prod f(p_i^{k_i})\)，若 \(f(x)\) 为完全积性函数，则 \(f(x)=\prod f(p_i)^{k_i}\)。

常见的积性函数

单位函数 \(\varepsilon(n)=[n=1]\) (完全积性)

恒等函数 \(id_k(n)=n^k\) (完全积性)

常数函数 \(I(n)=1\) (完全积性)

除数函数 \(\sigma_k(n)=\sum_{d|n}d^k\) (积性)，\(\sigma_0(n)=d(n)\)

欧拉函数 \(\varphi(n)=\sum_{i=1}^n[\gcd(i,n)=1]\) (积性)

莫比乌斯函数 \(\begin{equation}\mu(n)=\begin{cases}1&&n=1\\{(-1)}^r&&n=p_1*p_2*…p_r(\text{无平方因数})\\0&&else\end{cases}\nonumber\end{equation}\) (积性和加性)

狄利克雷卷积

满足交换律，结合律，分配律

两个积性函数的狄利克雷卷积还是积性函数

完全积性函数 \(g\) 和 积性函数 \(f\cdot g\) 的卷积 \(g\ast(f\cdot g)=(f\ast I)\cdot g\)

公式

A-你也喜欢数学吗_2023河南萌新联赛第（一）场：河南农业大学