质数、约数、欧拉函数基础知识

不想做题了，那就来总结吧

0X00 质数

判断一个数字是不是质数

可以用试除法 $O(\sqrt{n})$ 原因是一个数的约数是成队出现的 $\sqrt{n}$ 之前有一半， $\sqrt{n}$ 之后有一半，如果 $\sqrt{n}$ 之前都没有，那就一定是一个质数

筛法求质数

用质数的倍数去筛

# 只用质数去筛
# O(nlognlogn)
def getPrimes2(n):
  for i in range(2, n+1):
    if st[i]:
      primes[cnt] = i
      cnt += 1
      for j in range(i, n+1, i):
        st[j] = False

其中有一些很重要的定理：

调和级数 $1 + \frac{1}{2} + \frac{1}{3} + ... + \frac{1}{n} \approx ln(n) + c$

1 ~ n 之间质数的个数为 $\frac{n}{ln(n)}$

用最小质因数筛

# 用最小质因数去筛
# O(n) 因为每个数只会被筛一次
def getPrimes3(n):
  global cnt
  for i in range(2, n+1):
    if st[i]:
      primes[cnt] = i
      cnt += 1
    j = 0
    while primes[j] <= n // i:
      # 用最小质因子去筛
      st[primes[j]*i] = False
      # 当 i % pj == 0 时 如果再继续就会用 i * p(j+1) 去筛 由于 i % pj == 0 所以之后的就不是最小质因子了
      # 所以要 break
      if i % primes[j] == 0: break
      
      j += 1

0X01 约数

约数个数

我们知道一个数可以写成： $n = p_1^{\alpha_1}p_2^{\alpha_2}...p_n^{\alpha_n}$

由乘法原理可得，一个数的约数个数是：

$(1+\alpha_1)(1+\alpha_2)...(1+\alpha_n)$

求所有约数

求出一个数的所有质因子，就可已通过 dfs 求出所有的约数

约数之和

可以通过 dfs 求出所有约数以后，算出约数之和
也可以通过公式算出约数之和

$sum = (p_1^{0} + p_1^{1}+...+p_1^{\alpha_1})(p_2^{0} + p_2^{1}+...+p_2^{\alpha_2})...(p_n^{0} + p_n^{1}+...+p_n^{\alpha_n})$

最大公约数与最小公倍数

我们把「最大公约数」叫做 gcd 把最小公倍数叫做 lcm

通过「欧几里得算法」求出最大公约数

def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

且有

$a * b = gcd(a, b) * lcm(a, b)$

一些常识

1e9 之内一个数的最多约数不会超过 1500 见反素数

0X02 欧拉函数

如何求出欧拉函数

设 n 为正整数，以 φ(n) 表示不超过 n 且与 n 互素的正整数的个数，称为 n 的欧拉函数值，比如 $\phi(4) = 2$ 因为 4 与 1 和 3 互质

可见的点

def getPs(n):
    for i in range(2, n+1):
        if st[i]:
            ps.append(i)
            phi[i] = i - 1
        j = 0
        while ps[j] <= n // i:
            st[i * ps[j]] = False
            if not i % ps[j]:
                phi[i * ps[j]] = phi[i] * ps[j] 
                break
            phi[i * ps[j]] = (ps[j] - 1)*phi[i]
            j += 1

T = int(input())
N = 1010
ps = []
phi = [0] * (N+1)
phi[1] = 1
st = [True] * N
sums = [0] * (N+1)
getPs(1000)

for i in range(1, N+1):
    sums[i] = phi[i] + sums[i-1]

for i in range(T):
    t = int(input())
    print(i+1, t, 2 * sums[t] + 1)