Acwing数学知识——学习笔记_每个正整数都能够以唯一的方式表示成它的质因数的乘积

ACwing数学知识听课笔记

---

质数

试除法求素数

试除法判断质数
一个最朴素的想法就是判断给定的数num % range(2, n - 1) == 0？若是，则说明除了1和它本身还有其他约数，则非质数，反之则是质数，这样的朴素算法是O(n)的

但是对于一个数num来说，存在这样的一个性质：若d是num的约数，则num/d依然是num的约数，这样一来，我们枚举的区间就可以变成(2, 根号下num)，大大减少了时间复杂度

import math
def isprime(n):
      if n==1:
            return False
      for i in range(2, int(math.sqrt(n) + 1)):
	    if n % i == 0:
	          return False
      return True
1
2
3
4
5
6
7
8

分解质因数

题目：https://www.acwing.com/problem/content/869/
概念：

• 不考虑排列顺序的情况下，每个正整数都能够以唯一的方式表示成它的质因数的乘积。任何数都可以表示成 唯一的 质数的乘积。
  n=p1^a1 x p2^a2 x p3^a3x 。。。。 pn^an pk是质数

比如一个数16 在分解时先找到2这个质因子，然后由于16/2后还可以/2，所以会在2这个质因子上产生次方
不优化版本：从2~n 找到能整除的因子然后算次方

#TLE了O(n)
import math as m
def divide(x):
    # 和小学做分解素因数是一样的过程
    for k in range(2,x+1):
        if x % k == 0:#只要成立 k一定是质数！假如 k 是一个合数，那么它一定可以分解成多个质因子相乘的形式，这多个质因子同时也是 x 的质因子且比 k要小，而比 k小的数在之前的循环过程中一定是被条件除完了的，所以 k不可能是合数，只可能是质数
            s = 0
            while x % k == 0:
                x /= k
                s += 1
            print(k,s)
    print()

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

• 有个性质：n中最多只含有一个大于sqrt(n)的质因子。证明通过反证法：如果有两个大于sqrt(n)的因子，那么相乘会大于n，矛盾。证毕

板子

#O(sqrtn)
import math as m
def divide(x):
    for k in range(2,int(m.sqrt(x))+1): #先把所有小于sqrtn的质因子枚举出来
        if x % k == 0:
            s = 0
            while x % k == 0:
                x /= k
                s += 1
            print(k,s)
    if x > 1:
        print(int(x),1)#最后如果n还是>1，说明这就是大于sqrt(n)的那个质因子，输出即可。
    print()
    
n = int(input())
while n > 0:
    x = int(input())
    divide(x)
    n -= 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

• 两个没有共同质因子的正整数称为互质。因为 1 没有质因子，1与任何正整数（包括 1 本身）都是互质。
• 只有一个质因子的正整数为质数。

质数筛

题目：https://www.acwing.com/activity/content/problem/content/937/

朴素筛法——每一个数都把自己的倍数全部筛除

def find_prime(n):
    cnt = 0
    for x in range(2,n+1):
        if is_prime[x]:
            cnt += 1
        for i in range(2*x,n+1,x):#从x的倍数开始，每次步长x，把所有x的倍数筛掉
            is_prime[i] = False
    return cnt
    
if __name__ == "__main__":
    is_prime = [True] * 1000010
    n = int(input())
    print(find_prime(n))

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

埃氏筛法—把所有质数的倍数全部删除（用这个就行了）

原理：
合数必然是某个或某几个质数的倍数。那么这个合数的倍数当然也就是这个合数质因数的倍数了。所以这个合数的倍数都在其质因数的倍数中已经包括了

def find_prime(n):
    cnt = 0
    for x in range(2,n+1):
        if is_prime[x]:
            cnt += 1
        else:
            # 是合数，不删合数的倍数 合数一定可以表示为质因子相成，一定是质数的倍数！
            continue
        for i in range(2*x,n+1,x):
            is_prime[i] = False
    return cnt

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

线性筛法—每个合数只能被自己的最小质因数删除（没了解）

约数

试除法求约数

板子

优化，d | n 的话 （d能被n整除），那么n/d | n ；例如 2 ｜6 =》 6/2 ｜6=3｜6
约数肯定是成对出现的，只需要枚举较小的那个约数！

def get_dividors(x):
    q=[]
    for i in range(1,int(math.sqrt(x))+1):#i>x/i 的情况是另一个约数,此时i>sqrt(x)
        if x%i==0:#i是一个约数
            q.append(i)
            if i!=x//i:#当前是另一个对称的约数
                q.append(x//i)
    q.sort()
    return q
1
2
3
4
5
6
7
8
9

直接对for循环改写，注意python

AcWing 869.试除法求约数

传送门

AcWing 870. 约数个数

基本思想：
如果 N = p1^c1 * p2^c2 * … *pk^ck
约数个数： (c1 + 1) * (c2 + 1) * … * (ck + 1)
约数之和： (p1^0 + p1^1 + … + p1^c1) * … * (pk^0 + pk^1 + … + pk^ck)

步骤：
1. 对N进行隐式分解，并存入数组对应记录次数（试除法）
2. 根据公式计算约数的个数

from collections import defaultdict
import math
M=int(1e9+7)

def get_Prime(x):#寻找质因数
    for i in range(2,int(math.sqrt(x))+1):
        while x%i==0:
            x/=i
            primes[i] +=1#primes[2]=3 对应x的2质因数是3次
    if x>1:
        primes[x]+=1#一个数n最多只包含一个大于sqrt(n)的质数，所以x>1，表示x是这个大的质数


n=int(input())
primes,ans=defaultdict(int),1
for i in range(n):
    m=int(input())
    get_Prime(m)#每一个数的质因数都记录在primes上，而不是先乘再记录，类似埃式筛
for i in primes.values():
    #print(i)
    ans=ans*(i+1)%M#约数 (c1 + 1) * (c2 + 1) * ... * (ck + 1) 记得mod

print(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

AcWing 871. 约数之和

套用约数和公式！注意输入的数数1e9级的，用快速幂！

from collections import defaultdict
import math
M=10**9 +7

def get_Prime(x):#寻找质因数
    for i in range(2,int(math.sqrt(x))+1):
        while x%i==0:
            x/=i
            primes[i] +=1#primes[2]=3 对应x的2质因数是3次
    if x>1:
        primes[x]+=1#一个数n最多只包含一个大于sqrt(n)的质数，所以x>1，表示x是这个大的质数

def fpowx(x, n):
    res = 1
    while n:
        if n & 1:
            res = res * x
        # compute x^2 x^4 x^8
        x *= x
        n >>= 1
    return res

n=int(input())
primes,ans=defaultdict(int),0
res=1
for i in range(n):
    m=int(input())
    get_Prime(m)#每一个数的质因数都记录在primes上，而不是先乘再记录，类似埃式筛
for i in primes.keys():
    ans =0
    for x in range(0,primes[i]+1):
        ans = ans + (int(fpowx(i,x)))%M
    res=res*(ans)%M
print(res)


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
32
33
34
35
36

AcWing 872. 最大公约数(欧几里得算法（辗转相除法）)

原理：gcd(a,b) = gcd(b,a mod b)
一直进行上述过程，直到b(余数)为0时，输出a(最大公约数)

gcd最大公约数板子：

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

1
2
3
4
5

直接用python的math.gcd,效率更快！