蓝桥杯省赛7日集训-简单数论 Day1-Day2

这篇具有很好参考价值的文章主要介绍了蓝桥杯省赛7日集训-简单数论 Day1-Day2。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

蓝桥杯省赛7日集训-简单数论 Day1-Day2

一、质因数分解

蓝桥杯省赛7日集训-简单数论 Day1-Day2

这是一个比较简单的质因数分解问题,可以使用试除法求解。具体实现过程如下:

  1. 从标准输入中读取正整数 n。
  2. 从 2 开始依次尝试将 n 进行除法运算,如果 n 能够被当前的数整除,则说明当前数是 n 的一个质因数,将 n 除以当前数,然后继续尝试除以当前数,直到 n 不能被当前数整除为止。
  3. 最后得到的 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 列表中,并将其所有的倍数标记为合数,如果当前数是某个质数的倍数,则不需要再将其标记为合数,直接跳过即可。

二、质数

蓝桥杯省赛7日集训-简单数论 Day1-Day2

这是一个求解质数的问题,可以使用质数筛法求解。具体实现过程如下:

  1. 从标准输入中读取正整数 N。
  2. 使用质数筛法求解区间 [2, N) 中的所有质数,同时统计质数的个数。
  3. 输出所有的质数,每两个质数之间用一个空格隔开,然后输出质数的个数。

下面是 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位

蓝桥杯省赛7日集训-简单数论 Day1-Day2

我们可以使用快速幂和取模运算求解。具体实现过程如下:

  1. 从标准输入中读取三个整数 a、b、n,分别表示被除数、除数和所求小数点后第 n 位开始的位置。
  2. 计算 mod = b * 1000,这是因为我们需要计算小数点后第 n 位开始的 3 位数字,而每一位数字的范围是 [0, 999],因此需要计算出一个 mod 值,使得 a/b * pow(10, n+2) % mod 的结果在 [0, 999] 范围内。
  3. 计算 a * pow(10, n+2, mod) % mod,这是计算 a/b 的近似值,其中 pow(10, n+2, mod) 表示计算 10^(n+2) 对 mod 取模的结果,这样可以避免计算过程中出现整数溢出的问题。
  4. 将计算结果除以 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 位数字。

四、棋盘放麦子

蓝桥杯省赛7日集训-简单数论 Day1-Day2

这是一个经典的数学问题,可以使用循环求解。具体实现过程如下:

  1. 定义一个变量 total,表示需要的总麦粒数,初始值为 0。
  2. 使用一个循环,从 1 到 64 枚举每个棋盘格,将当前棋盘格应该放的麦粒数加到 total 变量中。
  3. 输出 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)

五、等差数列

蓝桥杯省赛7日集训-简单数论 Day1-Day2

具体实现过程如下:

  1. 从标准输入中读取整数 N 和 N 个整数 a1, a2, …, an。
  2. 对这 N 个整数进行排序。
  3. 定义一个变量 d,初始值为 1e9,表示公差的最大值。
  4. 遍历排序后的整数列表,计算相邻两个整数之间的差值,然后将其更新到变量 d 中,得到所有相邻整数之间的最小差值,即为公差。
  5. 如果公差为 0,说明所有数都相等,直接输出列表长度。
  6. 如果公差不为 0,说明有不同的数,计算包含给定整数的最短等差数列的长度,即为 (l[-1] - l[0])/d + 1。
  7. 输出计算结果。

下面是 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。最后输出计算结果即可。

六、数数

蓝桥杯省赛7日集训-简单数论 Day1-Day2

这是一个比较典型的质数分解问题,可以使用质因数分解的方法求解。具体实现过程如下:

首先需要预处理出区间 [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 的值即可。

但是上述代码运行时间太长了,我们需要继续优化。

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模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 第十三届蓝桥杯省赛Python 组

    本次所有代码均存放于仓库: Github :GxlHus/Algorithm at 蓝桥杯 (github.com) Gitee :Algorithm: 算法解题 - Gitee.com 原题目:第十三届蓝桥杯大赛软件赛省赛_PB.pdf · AYO/Algorithm - Gitee.com 本次省赛题目总体来说不难,总体质量比较高,尤其是后边几道题,虽然能轻易做出来,但是想跑通所

    2023年04月17日
    浏览(47)
  • 蓝桥杯省赛无忧 STL 课件13 list

    以下是一个示例,展示如何使用listt容器: 在上述示例中,我们首先创建了一个list容器myList,然 后使用push_back()和push_front()函数分别在链表尾部和头 部插入元素。最后,使用范围基于范围的for循环遍历链 表并输出元素。 需要注意的是,由于list是双向链表,因此插入和删除操

    2024年02月02日
    浏览(38)
  • 蓝桥杯省赛PREV-348试题1:算术填符号

    资源限制 内存限制:256.0MB   C/C++时间限制:1.0s   Java时间限制:3.0s   Python时间限制:5.0s 匪警请拨110,即使手机欠费也可拨通! 为了保障社会秩序,保护人民群众生命财产安全,警察叔叔需要与罪犯斗智斗勇,因而需要经常性地进行体力训练和智力训练! 某批警察叔叔正在

    2023年04月09日
    浏览(40)
  • 2019 第十届蓝桥杯省赛A组题解

    本次试题难度(对专业算法竞赛选手来说)不大,但是考验基本的编程基本功和数学思维。估计完成80%即可获得省一进入决赛(根据一些公开的反馈,如果有准确数据请告诉我),因此更多的是需要细心。 至于C/C++还是Java我觉得不重要,因为题目除了顺序有点不同,内容是一

    2023年04月09日
    浏览(46)
  • 第九届蓝桥杯省赛——3字母阵列(二维数组)

    仔细寻找,会发现:在下面的8x8的方阵中,隐藏着字母序列:“LANQIAO”。 SLANQIAO ZOEXCCGB MOAYWKHI BCCIPLJQ SLANQIAO RSFWFNYA XIFZVWAL COAIQNAL 我们约定: 序列可以水平,垂直,或者是斜向; 并且走向不限(实际上就是有一共8种方向)。 上图中一共有4个满足要求的串。 下面有一个更大的

    2024年02月15日
    浏览(45)
  • 【十三届蓝桥杯省赛解析javaC组】

    题目描述 解题思路 A题相对比较简单,这题有两种解法 第一种是可以利用记事本把文本复制,然后自己手动排序 第二种是写代码:具体思路是定义一个字符串用来储存问文本,然后把文本转成字符型数组,利用Arrays.sort对字符型数组进行排序,最终实现字符的排序 代码示例

    2023年04月20日
    浏览(42)
  • 【蓝桥杯省赛真题18】python阴影图形面积 青少年组蓝桥杯python编程省赛真题解析

    目录 python阴影图形面积 一、题目要求 1、编程实现 2、输入输出

    2023年04月23日
    浏览(44)
  • 第十四届蓝桥杯省赛PythonA/C组------翻转

    小蓝用黑白棋的n个棋子排成了一行,他在脑海里想象出了一个长度为n的01串T,他发现如果把黑棋当做1,白棋当做0,这一行棋子也是一个长度为n 的01串S。 小蓝决定,如果在S中发现一个棋子和它两边的棋子都不一样,就可以将其翻转变成另一个颜色。也就是说,如果S中存在

    2024年01月22日
    浏览(53)
  • 最小剩余空间-第11届蓝桥杯省赛Python真题精选

    [导读]:超平老师的Scratch蓝桥杯真题解读系列在推出之后,受到了广大老师和家长的好评,非常感谢各位的认可和厚爱。作为回馈,超平老师计划推出《Python 蓝桥杯真题解析100讲》, 这是解读系列的第31讲。 最小剩余空间, 本题是2020年6月20日举办的第11届蓝桥杯青少组Pyt

    2024年01月17日
    浏览(49)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包