蓝桥杯省赛7日集训-简单数论 Day1-Day2
一、质因数分解
这是一个比较简单的质因数分解问题,可以使用试除法求解。具体实现过程如下:
- 从标准输入中读取正整数 n。
- 从 2 开始依次尝试将 n 进行除法运算,如果 n 能够被当前的数整除,则说明当前数是 n 的一个质因数,将 n 除以当前数,然后继续尝试除以当前数,直到 n 不能被当前数整除为止。
- 最后得到的 n 就是较大的那个质数。
下面是 Python 代码实现:
n = int(input())
for i in range(2, int(n ** 0.5) + 1):
if n % i == 0:
print(n // i)
break
其中,int(n ** 0.5) + 1
表示区间 [2, n] 中的所有可能的质因数,从小到大依次尝试将 n 进行除法运算,如果 n 能够被当前的数整除,则说明当前数是 n 的一个质因数,将 n 除以当前数,然后继续尝试除以当前数,直到 n 不能被当前数整除为止。最后得到的 n 就是较大的那个质数。
质数筛选法
质数筛法是一种常见的求解质数的算法,常见的有埃氏筛法、欧拉筛法和线性筛法。下面分别介绍这三种算法的实现过程和 Python 代码:
- 埃氏筛法
埃氏筛法是最简单的一种质数筛法,其基本思想是从小到大枚举每个数,如果这个数是质数,则将其所有的倍数标记为合数。具体实现过程如下:
def sieve(n):
is_prime = [True] * (n + 1)
is_prime[0] = is_prime[1] = False
for i in range(2, n + 1):
if is_prime[i]:
for j in range(i * i, n + 1, i):
is_prime[j] = False
return [i for i in range(n + 1) if is_prime[i]]
其中is_prime
列表用于存储每个数是否为质数,初始时所有数都被标记为质数,然后从 2 开始枚举每个数,如果当前数是质数,则将其所有的倍数标记为合数,最后返回所有质数的列表。
- 欧拉筛法
欧拉筛法是一种优化的质数筛法,其基本思想是从小到大枚举每个质数,然后将其所有的倍数标记为合数。具体实现过程如下:
def sieve(n):
is_prime = [True] * (n + 1)
primes = []
for i in range(2, n + 1):
if is_prime[i]:
primes.append(i)
for p in primes:
if i * p > n:
break
is_prime[i * p] = False
if i % p == 0:
break
return primes
其中primes
列表用于存储当前已经找到的所有质数,初始时为空,然后从 2 开始枚举每个数,如果当前数是质数,则将其加入到 primes
列表中,并将其所有的倍数标记为合数,如果当前数是某个质数的倍数,则不需要再将其标记为合数,直接跳过即可。
- 线性筛法
线性筛法是一种更加高效的质数筛法,其基本思想是从小到大枚举每个数,如果当前数是质数,则将其加入到质数列表中,并将其所有的倍数标记为合数,如果当前数是某个质数的倍数,则不需要再将其标记为合数,直接跳过即可。具体实现过程如下:
def sieve(n):
is_prime = [True] * (n + 1)
primes = []
for i in range(2, n + 1):
if is_prime[i]:
primes.append(i)
for p in primes:
if i * p > n:
break
is_prime[i * p] = False
if i % p == 0:
break
return primes
其中primes
列表用于存储当前已经找到的所有质数,初始时为空,然后从 2 开始枚举每个数,如果当前数是质数,则将其加入到 primes
列表中,并将其所有的倍数标记为合数,如果当前数是某个质数的倍数,则不需要再将其标记为合数,直接跳过即可。
二、质数
这是一个求解质数的问题,可以使用质数筛法求解。具体实现过程如下:
- 从标准输入中读取正整数 N。
- 使用质数筛法求解区间 [2, N) 中的所有质数,同时统计质数的个数。
- 输出所有的质数,每两个质数之间用一个空格隔开,然后输出质数的个数。
下面是 Python 代码实现:
def sieve(n):
is_prime = [True] * n
primes = []
for i in range(2, n):
if is_prime[i]:
primes.append(i)
for j in range(i * i, n, i):
is_prime[j] = False
return primes
n = int(input())
primes = sieve(n)
print(' '.join(map(str, primes)))
print(len(primes))
其中is_prime
列表用于存储每个数是否为质数,初始时所有数都被标记为质数,然后从 2 开始枚举每个数,如果当前数是质数,则将其加入到 primes
列表中,并将其所有的倍数标记为合数。最后输出所有的质数,每两个质数之间用一个空格隔开,然后输出质数的个数。
三、小数第n位
我们可以使用快速幂和取模运算求解。具体实现过程如下:
- 从标准输入中读取三个整数 a、b、n,分别表示被除数、除数和所求小数点后第 n 位开始的位置。
- 计算 mod = b * 1000,这是因为我们需要计算小数点后第 n 位开始的 3 位数字,而每一位数字的范围是 [0, 999],因此需要计算出一个 mod 值,使得 a/b * pow(10, n+2) % mod 的结果在 [0, 999] 范围内。
- 计算 a * pow(10, n+2, mod) % mod,这是计算 a/b 的近似值,其中 pow(10, n+2, mod) 表示计算 10^(n+2) 对 mod 取模的结果,这样可以避免计算过程中出现整数溢出的问题。
- 将计算结果除以 b,得到小数部分的近似值,然后再将结果整除 1000,得到小数点后第 n 位开始的 3 位数字。
下面是 Python 代码实现:
a, b, n = map(int, input().split())
mod = b * 1000
res = a * (pow(10, n+2, mod)) % mod // b
print(res)
其中pow(10, n+2, mod)
表示计算 10^(n+2) 对 mod 取模的结果,这样可以避免计算过程中出现整数溢出的问题。最后将计算结果除以 b,得到小数部分的近似值,然后再将结果整除 1000,得到小数点后第 n 位开始的 3 位数字。
四、棋盘放麦子
这是一个经典的数学问题,可以使用循环求解。具体实现过程如下:
- 定义一个变量
total
,表示需要的总麦粒数,初始值为 0。 - 使用一个循环,从 1 到 64 枚举每个棋盘格,将当前棋盘格应该放的麦粒数加到
total
变量中。 - 输出
total
的值。
下面是 Python 代码实现:
total = 0
for i in range(1, 65):
total += 2 ** (i - 1)
print(total)
其中2 ** (i - 1)
表示第 i 个棋盘格应该放的麦粒数,将其加到 total
变量中,最后输出 total
的值即可。
因为这也是一个等比数列求和的问题,所以我们还可以使用等比数列的求和公式进行解决:
a1 = 1
res = a1*((1-2**64)//(1-2))
print(res)
五、等差数列
具体实现过程如下:
- 从标准输入中读取整数 N 和 N 个整数 a1, a2, …, an。
- 对这 N 个整数进行排序。
- 定义一个变量 d,初始值为 1e9,表示公差的最大值。
- 遍历排序后的整数列表,计算相邻两个整数之间的差值,然后将其更新到变量 d 中,得到所有相邻整数之间的最小差值,即为公差。
- 如果公差为 0,说明所有数都相等,直接输出列表长度。
- 如果公差不为 0,说明有不同的数,计算包含给定整数的最短等差数列的长度,即为 (l[-1] - l[0])/d + 1。
- 输出计算结果。
下面是 Python 代码实现:
n = int(input())
l = sorted(list(map(int, input().split())))
d = 1e9 # d表示公差
for i in range(n - 1):
d = min(d, l[i + 1] - l[i]) # 找能取到的最大公差
if d == 0: # 公差为0,说明所有数都相等
print(len(l)) # 直接输出长度
else: # 公差不为0,说明有不同的数
print(int((l[-1] - l[0]) / d + 1))
其中,d
变量表示公差的最大值,初始值为 1e9,表示公差的最大值不可能超过 1e9。遍历排序后的整数列表,计算相邻两个整数之间的差值,然后将其更新到变量 d
中,得到所有相邻整数之间的最小差值,即为公差。如果公差为 0,说明所有数都相等,直接输出列表长度。如果公差不为 0,说明有不同的数,计算包含给定整数的最短等差数列的长度,即为 (l[-1] - l[0])/d + 1。最后输出计算结果即可。
六、数数
这是一个比较典型的质数分解问题,可以使用质因数分解的方法求解。具体实现过程如下:
首先需要预处理出区间 [2, 23333333] 中的所有质数,可以使用筛法求解。
对于区间 [2333333, 23333333] 中的每个正整数,可以使用质因数分解的方法将其分解为若干个质数相乘,然后判断质数的个数是否为 12,如果是则计数器加 1。
下面是 Python 代码实现:
def sieve(n):
is_prime = [True] * (n + 1)
is_prime[0] = is_prime[1] = False
for i in range(2, int(n ** 0.5) + 1):
if is_prime[i]:
for j in range(i * i, n + 1, i):
is_prime[j] = False
return [i for i in range(n + 1) if is_prime[i]]
primes = sieve(23333333)
count = 0
for num in range(2333333, 23333334):
factors = []
for p in primes:
if p * p > num:
break
while num % p == 0:
num //= p
factors.append(p)
if num > 1:
factors.append(num)
if len(factors) == 12:
count += 1
print(count)
sieve(n) 函数使用筛法求解区间 [2, n] 中的所有质数,primes 列表存储了区间 [2, 23333333] 中的所有质数,num 表示当前需要判断的正整数,factors 列表存储了 num 的所有质因数,如果 factors 的长度为 12,则说明 num 可以被分解为 12 个质数相乘,计数器 count 加 1。最后输出 count 的值即可。
但是上述代码运行时间太长了,我们需要继续优化。文章来源:https://www.toymoban.com/news/detail-400167.html
cnt = 0
start = 2333333
end = 23333333
factor = [0] * (end + 1) # factor[i]表示i的质因子个数
prime = [] # 存储所有质数
for i in range(2, end + 1): # 筛法求质数
if factor[i] == 0: # i是质数
factor[i] = 1 # i的质因子个数为1
prime.append(i) # 将i加入质数表
if i >= start and factor[i] == 12: # i是质数且在区间内
cnt += 1 # 答案加1
for p in prime: # 遍历质数表
if i * p > end: # 超出范围,跳出循环
break
factor[i * p] = factor[i] + 1 # i*p的质因子个数为i的质因子个数+1
if i % p == 0: # i是p的倍数
break
print(cnt)
其中,factor
数组用于存储每个数的质因子个数,初始时所有数的质因子个数都为 0。prime
列表用于存储所有的质数。使用筛法求出区间 [2, end] 中的所有质数,并将它们加入 prime
列表中。对于每个质数 p,遍历区间 [2, end] 中所有的 p 的倍数,将它们的质因子个数更新为 p 的质因子个数加 1。遍历区间 [start, end] 中的每个数,如果它的质因子个数为 12,则将计数器 cnt
加 1。最后输出计数器 cnt
的值即可。
第二种方法可以在较短的时间内输出答案,但还是超时了,不过这道题目只是一道填空题所以直接填写答案即可,目前还没有想到可以提交通过的答案。文章来源地址https://www.toymoban.com/news/detail-400167.html
到了这里,关于蓝桥杯省赛7日集训-简单数论 Day1-Day2的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!