素数 & 约数 & 幂 & 阶乘
一、素数
素数又称质数，一个大于1且只能被1和它本身整除的数被称为素数。对素数的求解往往是解决素数和约数问题的基础。
（1）求解方法
素数的求解有试除法、埃氏筛和线性筛三种求法，其中线性筛效率最高，此处只列出线性筛代码，因为线性筛不仅效率高，还可以方便地求出每个数的最小质因数，用途更广。
注意在考试的时候尽量打表，蓝桥杯的内存限制比较宽，一般不会出现内存溢出。不要让素数的搜索占用宝贵的程序运行时间。
# 线性筛
def sieve(n):
# find out all of the prime numbers between 2 and n
prime = []
is_prime = [True]*(n+1)
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
if i%j == 0:
# 只用最小的质因数筛除非质数，减少了重复的运算
# 因为j已经筛过一遍了，所以不需要用i重复筛了
break
return prime
只需要对线性筛算法中筛除非质数的部分进行修改，在筛除某个值的同时记录筛除它的数即可
def sieve(n):
prime = []
is_prime = [True]*(n+1)
min_prime = [1]*(n+1)
for i in range(2,n+1):
if is_prime[i]:
prime.append(i)
# 素数的最小质因子是它本身
min_prime[i] = i
for j in prime:
if i*j > n:
break
is_prime[i*j] = False
# 在排除数字i*j的同时记录它的最小质因子j
# 注意此处i不一定是质数
min_prime[i*j] = j
if i%j == 0:
break
return min_prime
（2）求最小质因数
对于一个给定正整数，只需要从2开始逐个试除，第一个能够整除n的数就是其最小质因数。这个方法可以用反证法证明，如果第一个整除n的数是一个合数，那么n也一定可以被这个合数的每一个因数所整除，又因为合数存在小于其本身的因数，所以这个合数一定不是第一个能够整除n的数，这与假设矛盾，故原结论得证。
n = int(input())
for i in range(2,n+1):
if n%i == 0:
print(i)
break
（3）例题演示
例题：分解质因数
题目描述：
求出区间[a,b]中所有整数的质因数分解。
输入:
输入一行，包含两个用空格分割的正整数，分别表示 a 和 b。
输出:
每行输出一个数的分解，形如 k = a 1 ∗ a 2 ∗ a 3... k=a1* a2 *a3... k=a1∗a2∗a3... (a1<=a2<=a3…，k也是从小到大的)
# BF做法：直接对每一个在区间[a,b]内的数从2开始试除，但由于时间复杂度过高，一定会超时
# firstly,find out all the prime number that are smaller than n+1
def sieve(n):
prime = []
is_prime = [True]*(n+1)
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
if i%j == 0:
break
return prime
# main part
a,b = map(int,input().split())
prime = sieve(b)
# divide every number in the interval
for i in range(a, b+1):
print(f'{i} = ', end = '')
# create a string to store the result of division
line = []
for j in prime:
if i == 1:
break
while i%j == 0:
line.append(str(j))
line.append('*')
i //= j
# print the result of division
line.pop(-1)
print(''.join(line))
二、约数
约数又称因数，整数a除以非零整数b，除得的商正好是整数，余数为0，就说a能够被b整除，a是b的倍数，b是a的约数。
（1）求约数个数
约数个数定理：
对任意一个大于1的正整数 X X X 都可以表示为若干个质数乘积的格式，即 X = P 1 a 1 ∗ P 2 a 2 ∗ . . . ∗ P k a k X = P_1^{a_1} * P_2^{a_2} * ... * P_k^{a_k} X=P1a1∗P2a2∗...∗Pkak，则约数的个数就是 ( a 1 + 1 ) ∗ ( a 2 + 1 ) ∗ . . . ∗ ( a k + 1 ) (a_1 + 1)*(a_2 + 1)*...*(a_k + 1) (a1+1)∗(a2+1)∗...∗(ak+1)，注意这个结果中的约数包含1。
from collections import defaultdict
# calculate out the prime numbers that smaller than the given number
def sieve(n):
prime = []
is_prime = [True]*(n+1)
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
if i%j == 0:
break
return prime
n = int(input())
prime = sieve(n)
# divide the given number by these prime numbers
# use a defaultdict to record the times that every number appear in the given number
d = defaultdict(int)
for i in prime:
while n%i == 0:
d[i] += 1
n //= i
# use the data to figure out the answer
ans = 1
for i in d.values():
ans *= (i+1)
print(ans)
（2）求所有的约数
求约数的个数主要还是使用试除法，因为先计算所有质因数然后组合的时间复杂度过高，但也应注意到可以使用适当的优化提升算法的效率。
# BF algorithm
n = int(input())
res = []
for i in range(1, n+1):
if i > (n//i):
# all of the numbers that bigger than this value have alreadly been recorded
break
if n%i == 0:
res.append(i)
n //= i
# record the number that left as well
if n != i:
res.append(n)
res.sort()
print(res)
（3）最大公因数
求两个数的最大公因数的方法有辗转相除法和更相减损术等，此处只介绍应用范围更广且时间复杂度更小的辗转相除法。辗转相除法，又名欧几里得算法，是一种可以利用递归或递推快速求除出两数最大公因数的算法，时间复杂度为 O ( l o g n ) O(logn) O(logn)。
# 欧几里得算法
def gcd(a,b):
if b == 0:
return a
return gcd(b,a%b)
欧几里得算法既可以在考场时自己实现，也可以直接调用python的math标准库中的gcd()函数。
from math import gcd
m = 10
n = 6
print(gcd(m,n)) # output:2
（4）最小公倍数
求解定理：
最小公倍数 = 两数之积 // 最大公因数
from math import gcd
def gbs(a,b):
return a*b//gcd(a,b)
三、幂
幂的运算可以使用python的运算符**实现，也可以自行建立快速幂函数。快速幂算法的时间复杂度是 O ( l o g n ) O(logn) O(logn)
def qpow(a,n):
if n == 0:
return 1
res = 1
while n:
if n&1:
# n is an odd number
res = res * a
n >>= 1 # n need to be divided by 2
a = a * a
return res
四、阶乘
阶乘是蓝桥杯的高频考点，基本上每年都有一道题，大部分是简单填空题，但大题还是比较难的，
主要需要注意其递推特性( n ! = n ∗ ( n − 1 ) ! n! = n*(n-1)! n!=n∗(n−1)!)和n与约数之间的关系。这里列出两道题目，分别涵盖以上两个难点。
例题 1：求阶乘（蓝桥杯第13届省赛真题）
题目描述：
满足 N ! N! N! 的末尾恰好有 K K K 个0的最小的 N N N 是多少？输出这个数。如果这样的 N N N 不存在，输出-1
输入格式：
输入一行，包含一个整数，表示k
输出格式：
输出一行，包含一个整数
提示：
对于 30 % 30\% 30% 的数据， 1 ≤ K ≤ 1 0 6 1 \leq K \leq 10^6 1≤K≤106,
对于 100 % 100\% 100% 的数据， 1 ≤ K ≤ 1 0 18 1 \leq K \leq 10^{18} 1≤K≤1018
代码示例：
# 暴力做法，只能通过40%的样例
# 0只能通过乘以10的倍数或5的倍数获得，因为2的倍数远多于5的倍数，所以不用考虑
# 100，1200之类的数需要特别处理
from sys import exit
k = int(input())
if k < 0:
print(-1)
exit()
# 从5开始，以5为步长搜索5的倍数和10的倍数
n = 0 # 记录当前遍历到的因数
cur = 0 # 记录当前所得到的0的个数
while cur < k:
n += 5
# 先将n末尾所有的0转移到cur上
temp = n
while temp%10 == 0:
temp //= 10
cur += 1
# 然后统计temp中5的个数
while temp%5 == 0:
temp //= 5
cur += 1
if cur == k:
print(n)
else:
print(-1)
注意到对于一个给定的 n ! n! n!，末尾0的个数 = 从1到n各个数字的约数中5的个数 = k
k = n 5 1 + n 5 2 + n 5 3 + . . . k = \frac n {5^1} + \frac n {5^2} + \frac n {5^3} + ... k=51n+52n+53n+... 可以高效地求出指定n!的末尾0个数，所以可以使用二分法提高查找效率。
# Binary Search Optimize
# 注意到末尾0的个数随n的增大只会增大，不会减小，且结果的末尾0个数有大于等于k和小于k两种状态，所以可以使用二分法高效求解
def check(n):
# 求出 n! 末尾0的个数
res = 0
# 这个过程的实质是求出构成阶乘的数字中所有5的倍数，25的倍数，125的倍数...
while n:
n //= 5
res += n
return res
# binary search main part
k = int(input())
left = 1
right = 10**19
while left < right:
mid = (left+right)//2
if check(mid) < k:
left = mid+1
else:
# mid 可能是正确答案，所以不能舍弃
right = mid
# left = right
if check(left) == k:
# 存在解
print(left)
else:
print(-1)
例题 2：阶乘的和（蓝桥杯第14届省赛真题）
题目描述：
给定 n 个数 A i A_i Ai，问能满足 m! 为 ∑ i = 1 n ( A i ! ) ∑_{i=1}^n(A_i!) ∑i=1n(Ai!) 的因数的最大的 m 是多少。其中 m! 表示 m 的阶乘，即 1 × 2 × 3 × ⋅ ⋅ ⋅ × m 1 × 2 × 3 × · · · × m 1×2×3×⋅⋅⋅×m。
输入格式：
输入的第一行包含一个整数 n 。
第二行包含 n 个整数，分别表示 A i A_i Ai，相邻整数之间使用一个空格分隔。
输出格式：
输出一行包含一个整数表示答案。
提示：
对于 40 % 40\% 40% 的评测用例， n ≤ 5000 n ≤ 5000 n≤5000 ；
对于所有评测用例， 1 ≤ n ≤ 1 0 5 , 1 ≤ A i ≤ 1 0 9 1 ≤ n ≤ 10^5,1 ≤ A_i ≤ 10^9 1≤n≤105,1≤Ai≤109
解题思路：
在极限情况下，a数组中各个值均只出现一次，各阶乘无法合并，那么m! = a[0]!,a[0] = min(a)
本题中各个a[i]可能重复出现，因此存在合并阶乘的可能(比如n!*(n+1) = (n+1)!)，所以m! = min(s)
s是合并化简后的a数组各元素阶乘和式子中阶乘元素的集合
通过以上分析可知m!应当是分子中各个阶乘合并后最小的阶乘
通过分治求出合并后的最小阶乘
temp = (x*a[0] + y*(a[0]+1)),x,y分别是a[0],a[0]+1在a中的个数
显然a[0]<=m，现在要看合并结果是否是a[0]+1的倍数，(a[0]+1)*y显然是(a[0]+1)的倍数
倍数性质：m的倍数+不是m倍数的数，则结果一定不是m的倍数
由倍数定律可知如果x*a[0]是(a[0]+1)的倍数，则temp就是(a[0]+1)的倍数
又因为gcd(a[0],a[0]+1) = 1，所以‘x*a[0]是(a[0]+1)的倍数’等价于x是(a[0]+1)的倍数
n = int(input())
a = sorted([int(i) for i in input().split()])
# 从最小的a[0]开始递推
# 创建一个变量记录当前阶乘的系数
k = 1
# 创建一个变量记录当前阶乘的值
cur = a[0]
for i in range(1,n):
if cur == a[i]:
k += 1
else:
# cur < a[i]
# 检查系数是否能够合并进当前阶乘中
while k%(cur+1) == 0 and k//(cur+1) != 0:
cur += 1
k //= cur
if cur == a[i] :
break
# 无法达到a[i]
if cur < a[i]:
break
else:
# 成功到达a[i]
k += 1
print(cur)
