欢迎交流学习~~
专栏： 蓝桥杯Python组刷题日寄
蓝桥杯进阶系列：
🏆 Python | 蓝桥杯进阶第一卷——字符串
🔎 Python | 蓝桥杯进阶第二卷——贪心
💝 Python | 蓝桥杯进阶第三卷——动态规划
✈️ Python | 蓝桥杯进阶第四卷——图论
🌞 Python | 蓝桥杯进阶第五卷——数论
💎 Python | 蓝桥杯进阶第六卷——搜索
Python|蓝桥杯进阶第五卷——数论
- 🎁 买不到的数目
- 🌲 幂方分解
- 💡 麦森数
- 🍞 欧拉函数
🎁 买不到的数目
题目：
时间限制：
1s
内存限制：
128MB
题目描述：
小明开了一家糖果店。他别出心裁：把水果糖包成 4 颗一包和 7 颗一包的两种。糖果不能拆包卖。
小朋友来买糖的时候，他就用这两种包装来组合。当然有些糖果数目是无法组合出来的，比如要买 10 颗糖。
你可以用计算机测试一下，在这种包装情况下，最大不能买到的数量是17。大于17的任何数字都可以用 4 和 7 组合出来。
本题的要求就是在已知两个包装的数量时，求最大不能组合出的数字。
输入描述：
两个正整数，表示每种包装中糖的颗数(都不多于1000)
输出描述：
一个正整数，表示最大不能买到的糖数
样例输入：
4 7
样例输出：
17
解题思路
这里需要先确定上边界，然后针对小于其的数逐个判断即可。（代码1）
借助数论中的结论：自然数 a , b a,b a,b 互质,则不能表示成 a x + b y ax+by ax+by（ x , y x,y x,y 为非负整数）的最大整数是 a b − a − b ab-a-b ab−a−b，本题中所给出的数据全部为质数，因此可以使用。（代码2）
参考代码
# 代码1
from math import gcd
def check(a, b, n):
if n%a == 0 or n%b == 0:
return True
x = n//a
mod = n%a
for i in range(x+1):
if (i*a+mod)%b == 0:
return True
return False
def 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)
break
a, b = map(int, input().split())
func(a, b)
# 代码2
n,m = map(int, input().strip().split())
print(n*m-m-n)
🌲 幂方分解
题目：
时间限制：
1s
内存限制：
128MB
题目描述：
任何一个正整数都可以用 2 的幂次方表示。例如：
137=2^7+2^3+2^0
同时约定方次用括号来表示，即 ab 可表示为 a(b)。
由此可知，137 可表示为：
2(7)+2(3)+2(0)
进一步：7= 2^2+2+2^0 （2^1 用 2 表示）
3=2+2^0
所以最后 137 可表示为：
2(2(2)+2+2(0))+2(2+2(0))+2(0)
又如：
1315=2^10+2^8+2^5+2+2^0
所以 1315 最后可表示为：
2(2(2+2(0))+2)+2(2(2+2(0)))+2(2(2)+2(0))+2+2(0)
输入描述：
输入包含一个正整数 N（N<=20000），为要求分解的整数。
输出描述：
程序输出包含一行字符串，为符合约定的 n 的 0，2 表示（在表示中不能有空格）
样例输入：
1315
样例输出：
2(2(2+2(0))+2)+2(2(2+2(0)))+2(2(2)+2(0))+2+2(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 进制前面的 0b
n = 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 += '2+'
else:
# 其余情况，递归调用
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 个麦森数。最大的一个是p=3021377，它有 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 进行质因数分解，不妨设 n=p1^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)
