孝感市建设网站,网上推广专员是什么意思,网站开速度 流失,做原创短视频网站欢迎交流学习~~ 专栏#xff1a; 蓝桥杯Python组刷题日寄 蓝桥杯进阶系列#xff1a; #x1f3c6; Python | 蓝桥杯进阶第一卷——字符串 #x1f50e; Python | 蓝桥杯进阶第二卷——贪心 #x1f49d; Python | 蓝桥杯进阶第三卷——动态规划 ✈️ Python | 蓝桥杯进阶… 欢迎交流学习~~ 专栏 蓝桥杯Python组刷题日寄 蓝桥杯进阶系列 Python | 蓝桥杯进阶第一卷——字符串 Python | 蓝桥杯进阶第二卷——贪心 Python | 蓝桥杯进阶第三卷——动态规划 ✈️ Python | 蓝桥杯进阶第四卷——图论 Python | 蓝桥杯进阶第五卷——数论 Python | 蓝桥杯进阶第六卷——搜索 Python|蓝桥杯进阶第五卷——数论 买不到的数目 幂方分解 麦森数 欧拉函数买不到的数目
题目 时间限制 1s
内存限制 128MB
题目描述 小明开了一家糖果店。他别出心裁把水果糖包成 4 颗一包和 7 颗一包的两种。糖果不能拆包卖。 小朋友来买糖的时候他就用这两种包装来组合。当然有些糖果数目是无法组合出来的比如要买 10 颗糖。 你可以用计算机测试一下在这种包装情况下最大不能买到的数量是17。大于17的任何数字都可以用 4 和 7 组合出来。 本题的要求就是在已知两个包装的数量时求最大不能组合出的数字。
输入描述 两个正整数表示每种包装中糖的颗数(都不多于1000)
输出描述 一个正整数表示最大不能买到的糖数
样例输入 4 7
样例输出 17 解题思路 这里需要先确定上边界然后针对小于其的数逐个判断即可。代码1
借助数论中的结论自然数 a,ba,ba,b 互质,则不能表示成 axbyaxbyaxbyx,yx,yx,y 为非负整数的最大整数是 ab−a−bab-a-bab−a−b本题中所给出的数据全部为质数因此可以使用。代码2 参考代码
# 代码1
from math import gcd
def check(a, b, n):if n%a 0 or n%b 0:return Truex n//amod n%afor i in range(x1):if (i*amod)%b 0:return Truereturn Falsedef func(a, b):# 计算上边界这里取最小公倍数max_num (a*b)//gcd(a, b)for i in range(max_num-1, 0, -1):if not check(a, b, i):print(i)breaka, b map(int, input().split())
func(a, b)# 代码2
n,m map(int, input().strip().split())
print(n*m-m-n)幂方分解
题目 时间限制 1s
内存限制 128MB
题目描述 任何一个正整数都可以用 2 的幂次方表示。例如 1372^72^32^0 同时约定方次用括号来表示即 ab 可表示为 a(b)。
由此可知137 可表示为 2(7)2(3)2(0) 进一步7 2^222^0 2^1 用 2 表示 322^0 所以最后 137 可表示为 2(2(2)22(0))2(22(0))2(0)
又如 13152^102^82^522^0 所以 1315 最后可表示为 2(2(22(0))2)2(2(22(0)))2(2(2)2(0))22(0)
输入描述 输入包含一个正整数 NN20000为要求分解的整数。
输出描述 程序输出包含一行字符串为符合约定的 n 的 02 表示在表示中不能有空格
样例输入 1315
样例输出 2(2(22(0))2)2(2(22(0)))2(2(2)2(0))22(0) 解题思路 可以通过每个数的二进制来得到其二次幂分解 比如样例中的 1315其对应的二进制数为0b10100100011 其中 1 对应的位置由高到低为11 9 6 2 1 因此其对应二次幂分解为1315 2^10 2^8 2^5 2 ^1 2^0
对于 0 次幂和 1 次幂特别处理而对于高次幂通过递归调用。 注意要从高次幂开始处理。
具体见参考代码及其注释。 参考代码
def trans(n):# 转为 2 进制后再处理tmp list(bin(n))# 去除 2 进制前面的 0bn tmp[2:]# 转换为整数n [int(i) for i in n]res for i in range(1, len(n) 1):if n[len(n) - i]:if len(n) - i 0:# 处理 0 次幂res 2(0)elif len(n) - i 1:# 处理 1 次幂res 2else:# 其余情况递归调用res 2( trans(len(n) - i) )# 最后res会有一个 需要去除return res[:-1]if __name__ __main__:n int(input())print(trans(n))麦森数
题目 时间限制 3s
内存限制 192MB
题目描述 形如 2^p-1 的素数称为麦森数这时 p 一定也是个素数。但反过来不一定即如果 p 是个素数2^p-1不一定也是素数。到1998年底人们已找到了 37 个麦森数。最大的一个是p3021377它有 909526 位。麦森数有许多重要应用它与完全数密切相关。 任务从文件中输入 p(1000 p 3100000)计算 2^p-1 的位数和最后 500 位数字用十进制高精度数表示
输入描述 文件中只包含一个整数 p(1000 p 3100000)
输出描述 第一行十进制高精度数 2^p-1的位数。 第2-11行十进制高精度数 2^p-1 的最后 500 位数字。每行输出 50 位共输出 10 行不足 500 位时高位补 0 不必验证 2^p-1 与 p 是否为素数。
样例输入 1279
样例输出
386
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000104079321946643990819252403273640855
38615262247266704805319112350403608059673360298012
23944173232418484242161395428100779138356624832346
49081399066056773207629241295093892203457731833496
61583550472959420547689811211693677147548478866962
50138443826029173234888531116082853841658502825560
46662248318909188018470682222031405210266984354887
32958028878050869736186900714720710555703168729087 解题思路 对于一个十进制数 k其位数 A 为A int(log10(k) 1)
因为当 p 取较大值时整个数过大考虑到最后只需要输出 500 位我们将其对 10**500 取幂之后再按照要求格式输出。
具体见参考代码和注释。 参考代码
from math import log10 as lg
p int(input())
print(int(p * lg(2)) 1)num 2**p - 1
# 预处理因为最后只需要500位对 10**500 取幂
num num % (10**500)
res []
# 计算结果
for i in range(500):res.append(num % 10)num // 10# 按照要求打印
for i in range(499, -1, -1):print(res[i], end)if i % 50 0:print()欧拉函数
题目 时间限制 1s
内存限制 128MB
题目描述
给定一个大于 1不超过 2000000 的正整数 n输出欧拉函数phi(n) 的值。 如果你并不了解欧拉函数那么请参阅提示。
提示 欧拉函数 phi(n) 是数论中非常重要的一个函数其表示 1 到 n-1 之间与 n 互质的数的个数。显然的我们可以通过定义直接计算 phi(n)。 当然phi(n) 还有这么一种计算方法。 首先我们对 n 进行质因数分解不妨设 np1^a1 * p2^a2 * ... * pk^ak 这里 a^b 表示 a 的 b次幂p1 到 pk 为 k 个互不相同的质数a1 到 ak 均为正整数那么 phi(n)n(1-(1/p1))(1-(1/p2))....(1-(1/pk)) 稍稍化简一下就是 phi(n)n(p1-1)(p2-1)...(pk-1)/(p1*p2*...*pk)
计算的时候小心中间计算结果超过 int 类型上界可通过调整公式各项的计算顺序避免(比如先做除法)!
输入描述 在给定的输入文件中进行读入 一行一个正整数 n。 不超过 2000000 的正整数 n.
输出描述 将输出信息输出到指定的文件中: 一行一个整数表示 phi(n)。
样例输入 17
样例输出 16 解题思路 直接按照定义来写即可 参考代码
from math import gcd
n int(input())
count 0
for i in range(1,n):if gcd(i,n)1:count 1
print(count)
