• 數論，就是一些數學問題，藍橋杯十分喜歡考察，常見的數論的問題有：取模，同余，大整數分解，素數，質因數，最大公約數，最小公倍數等等

素數

• 首先介紹這個素數的問題，也就是質數，只能被1或者本身整除，最小的素數是2
• 需要掌握埃氏篩或者歐拉篩求解出1-n的范圍內的所有的質數

is_prime = [True]*(N+1)
prime = []
for i in range(2,N+1):if is_prime[i]:prime.append(i)for j in range(2*i,N+1,i):is_prime[j] = False
# 最后的話，這個prime 會存儲所有的質數

求解一個數的質因數

求解最小質因數

• 同樣，也可以使用埃氏篩，也可以使用歐式篩

def minprime(n):i = 2while i*i <= n:if n % i == 0:return ii += 1# 質數最后會返回自己本身return n

求解一個數的全部的質因數組成

def zuprime(n):ans = []i = 2while i*i <=n:while n % i == 0:ans.append(i)n = n // ii += 1if n > 1:ans.append(n)return ans

求解一個范圍內的數的最小質因數

使用歐式篩,歐式篩的原理就是，每一個數只會被最小質因數所篩選，所以相對于埃氏篩來說具有優勢

# 在這里我們初始化全部的數的最小質因數都是1，也包括質數
minprime = [1]*(N+1)
is_prime = [True]*(N+1)
prime = []
for i in range(2,N+1):if is_prime[i]:prime.append(i)for j in prime:if i*j > N :breakis_prime[i*j] = Falsemin_prime[i*j] = j# 保證只能被最小質因數篩選if i % j == 0:break

最大公因數

• a和b的最大公因數表示，可以整除a,b的最大的公因數，一般使用輾轉相除法進行求解

import math
# 需要求解a,b的最大公因數，可以直接調用這個gcd函數進行求解
ans = math.gcd(a,b)

最小公倍數

• a和b的最小公倍數LCM可以通過這個與最大公因數的關系進行求解

# lcm(a,b) = a*b // math.gcd(a,b)

組合數

快速冪

• 可以使用pow方法求解取模的冪次，類似于快速冪

result = pow(base, exponent, mod)  # 計算 (base ** exponent) % mod# 也可以手動實現上述功能
def quick_pow(a, n):ans = 1while n > 0:if n & 1:  # 如果該二進制位存在ans = ans * a % MODa = a * a % MODn >>= 1  # n除以2,判斷下一個二進制位return ans

容斥定理

錯位排序

習題

質數

找素數

• 由于是填空題，直接暴力求解

N = 10**7
prime = []
is_prime = [True]*(N+1)
for i in range(2,N+1):if is_prime[i]:prime.append(i)for j in range(i*2,N+1,i):is_prime[j] = False
if len(prime) > 10**5 +2 :print(prime[10**5+1])
# 1299743