蓝桥杯 之 数论

• 数论，就是一些数学问题，蓝桥杯十分喜欢考察，常见的数论的问题有：取模，同余，大整数分解，素数，质因数，最大公约数，最小公倍数等等

整除

取模

同余

• 两个数同余，就是a % k = b % k,对于对同一个数的同余，那么就意味着a = b + x*k,意味着它们相差k的倍数，也就有(a-b) % k = 0

素数

• 首先介绍这个素数的问题，也就是质数，只能被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

LCM

报数游戏

报数游戏

• 很明显，这个题目不可能会让你从一开始就进行大范围的暴力求解
• 所以还是考虑在小范围之内打表找规律

ans = []
for i in range(1,10**3+1):if i % 20 == 0 or i % 24 ==0:ans.append(i)
print(ans)
# 输出情况
[20, 24, 40, 48, 60, 72, 80, 96, 100, 120, 140, 144, 160, 168, 180, 192, 200, 216, 220, 240, 260, 264, 280, 288, 300, 312, 320, 336, 340, 360,····]

• 即使在打表之前，我们就应该想到，这个找的是20或者24的倍数，那么他们的倍数在什么时候会重合？这里就回到了这个LCM的问题，我们可以发现LCM(20,24)=120,所以对于打表之后的输出找规律，发现，刚好120范围就会有10个数字，类似于这个进制一样，我们只需算出n是10个多少倍数，然后再对应余数找到这个对应的基数，后面再乘再+即可

num = [20, 24, 40, 48, 60, 72, 80, 96, 100, 120]
print(202420242024//10)
# 答案是 20242024202
print(202420242024%10)
# 答案是 4print(120*20242024202+48)
# 答案是 2429042904288

快速幂

数字诗意

数字诗意

• 首先的思考，由于数字的范围十分大，所以考虑还是找规律，(其实数据范围较大的时候，就得考虑这个数字规律的问题，一般有幂次，循环规律等)
• 当然，还是老方法，通过打表进行求解，但是如何打表就成为我们现在应该考虑的问题！
• 暴力也是一种学问！：我们可以从1开始逐一枚举连续的和的开始位置，再枚举向右的位置

notres = []def check(num):# 枚举开始位置for i in range(1,num):ans = 0# 枚举结束的位置for j in range(i,num):ans += j if ans > num:breakelif ans == num:return True

直接暴力求解是可以通过30%的测试用例的

• 但是我们可以把打表的结果输出找规律！

# notres 数组如下
[1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192]
# 可以看到都是2的幂次，所以可以得到是2的幂次都是不满足的

• 现在的任务转化为这个快速求解出10^16那么大的一个范围内的2的幂次的值，然后存储起来，那么大的范围的一个幂次的问题，直接转化为这个快速幂的问题

# 10**16
notres = []
i = 0
# python直接调用这个pow函数进行求解
while pow(2,i) <= 10**16:notres.append(pow(2,i))i += 1

• 两个代码相互结合，就可以通过全部的测试用例

import os
import sys# 请在此输入您的代码notres = []# 10**16
notres = []
i = 0
while pow(2,i) <= 10**16:notres.append(pow(2,i))i += 1n = int(input())
a = list(map(int,input().split()))
cou = 0 
for nu in a:if nu in notres:cou+=1
print(cou)

组合数与错位排序

小蓝与钥匙

小蓝与钥匙

• 很容易看出来这是一个错位排序的问题，直接套公式dp[i] = (i-1)*(dp[i-1]+dp[i-2])
• 题目求解的是这个方案数，我们得在28个孩子中先选择14个孩子，作为错位排序的对象，剩余的就正常对应，所以这个还考察了这个组合数的问题

import os
import sys# 请在此输入您的代码# 错位排序+组合数
# 从28个孩子中选出14个孩子的方案数乘剩余14个错位排序的方案dp = [0]*15
dp[1] ,dp[2] = 0,1
for i in range(3,15):dp[i] = (i-1)*(dp[i-1]+dp[i-2])# 从28个孩子中选出14个孩子，28! // (14!*14!)tmp1 ,tmp2 = 1,1
for i in range(1,29):tmp1 *= i if i <= 14:tmp2 *= i
zu = int(tmp1 / (tmp2*tmp2))
print(dp[14]*zu)
# 答案是 1286583532342313400

同余

取模

取模

• 其实题目中的m的范围并没有那么大，我们直接采用暴力的做法即可

import os
import sys# 请在此输入您的代码# 取模，是否存在？
# 直接暴力求解
def check(num,m):store = set()for i in range(1,m+1):tmp = num % i if tmp in store:return Trueelse:store.add(tmp)return FalseT = int(input())
for _ in range(T):n,m = map(int,input().split())if check(n,m):print("Yes")else:print("No")