当前位置：首页 > article >正文

蓝桥杯之数论

article 2025/3/23 14:45:43

文章目录

习题
- 质数
- - 找素数
- LCM
- - 报数游戏
- 快速幂
- - 数字诗意
- 组合数与错位排序
- - 小蓝与钥匙
- 同余
- - 取模

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

整除
在这里插入图片描述

取模
在这里插入图片描述

同余

两个数同余，就是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 = 2
	while i*i <= n:
		if n % i == 0:
			return i
		i += 1
	# 质数最后会返回自己本身
	return n

求解一个数的全部的质因数组成
在这里插入图片描述

def zuprime(n):
	ans = []
	i = 2
	while i*i <=n:
		while n % i == 0:
			ans.append(i)
			n = n // i
		i += 1
	if 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 :
			break
		is_prime[i*j] = False
		min_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 = 1
    while n > 0:
        if n & 1:  # 如果该二进制位存在
            ans = ans * a % MOD
        a = a * a % MOD
        n >>= 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)
# 答案是 4

print(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:
        break
      elif 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 += 1

n = 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 True
    else:
      store.add(tmp)
  return False


T = int(input())
for _ in range(T):
  n,m = map(int,input().split())
  if check(n,m):
    print("Yes")
  else:
    print("No")