一、质数/素数问题判断一个数是不是质数def is_prime(n): if n 2: return False for i in range(2, int(n**0.5) 1): if n % i 0: return False return True题目描述实现一个算法求质数数目。介绍如下质数是指在大于 1 的自然数中除了 1 和它本身以外不再有其他因数的自然数。给定数字 nn对于从 0 至 nn 的数字需要判断这个数字是不是质数。然后输出质数总数。输入描述输入一个数字 n (1≤N≤105)n (1≤N≤105)含义见题干。输出描述输出一行为 0 至 n 之间质数的个数。输入输出示例输入5输出3def is_prime(n): if n2: return True for i in range(2,int((n**0.5)1)): if n%i0: return False return True count0 xint(input()) for i in range(2,x1): if is_prime(i): count1 print(count)二、最大公约数GCD/最小公倍数LCM最大公约数import math math.gcd(a, b)最小公倍数def lcm(a, b): return a * b // math.gcd(a, b)题目描述Hanks 博士是 BT (Bio-Tech生物技术) 领域的知名专家他的儿子名叫 Hankson。现在刚刚放学回家的 Hankson 正在思考一个有趣的问题。今天在课堂上老师讲解了如何求两个正整数 c1​ 和 c2 的最大公约数和最小公倍数。现在 Hankson 认为自己已经熟练地掌握了这些知识他开始思考一个“求公约数”和“求公倍数”之类问题的“逆问题”这个问题是这样的已知正整数 a0,a1,b0,b1设某未知正整数 x 满足x 和 a0的最大公约数是 a1x 和 b0 的最小公倍数是 b1。Hankson 的“逆问题”就是求出满足条件的正整数 x。但稍加思索之后他发现这样的 x 并不唯一甚至可能不存在。因此他转而开始考虑如何求解满足条件的 x的个数。请你帮助他编程求解这个问题。输入描述第一行为一个正整数 n表示有 n 组输入数据。接下来的 n 行每行一组输入数据为四个正整数 a0a1b0b1每两个整数之间用一个空格隔开。输入数据保证 a0能被 a1​ 整除b1 能被 b0 整除。其中保证有 1≤a0a1b0b1≤2×10^9且n≤2000。输出描述输出共 n 行。每组输入数据的输出结果占一行为一个整数。对于每组数据若不存在这样的 x请输出 0若存在这样的 x请输出满足条件的 x 的个数# 暴力求解时间复杂度高 import math def lcm(a,b): return a*b//math.gcd(a,b) def get_divisors(n): resset() for i in range(1,int(n**0.51)): if n%i0: res.add(i) # 问题一编写错误 # res.add(n%i) res.add(n//i) return sorted(res) nint(input()) # 问题二ans 变量定义在循环外导致每组数据的答案会累加应该每组重置 ans0 ans0 for _ in range(n): a0,a1,b0,b1map(int,input().split()) ans0 for x in (list(get_divisors(b1))): if math.gcd(x,a0)a1 and lcm(x,b0)b1: ans1 print(ans)三、约数/因数问题求一个数的所有约数def get_divisors(n): res set() for i in range(1, int(n**0.5)1): if n % i 0: res.add(i) res.add(n//i) return sorted(res)求约数个数def count_divisors(n): cnt 0 for i in range(1, int(n**0.5)1): if n % i 0: cnt 1 if i*i n else 2 return cnt四、快速幂def qpow(a, b, mod): res 1 a a % mod # 先取模防溢出 while b 0: # 如果二进制最后一位是1乘到结果 if b 1: res res * a % mod # a 平方 a a * a % mod # 指数右移一位除以2 b b 1 return res问题描述输入格式输出格式# 时间复杂度高导致运行超时 # import math # def lcm(a,b): # return a*b//math.gcd(a,b) # l,r map(int,input().split()) # ans0 # if (r-l)%20: # for i in range(l,r,2): # anslcm(i**i,(i1)**(i1)) # else: # for i in range(l,r,2): # anslcm(i**i,(i1)**(i1)) # ansr # print(ans%(10**97))import math def qpow (a,b,mod): res1 aa%mod while b0: if b1: resres*a%mod aa*a%mod bb1 return res l,rmap(int,input().split()) ans0 xqpow(l,l,10**97) for i in range(l1,r1): yqpow(i,i,10**97) ans((x*yans)%(10**97)) xy print(ans)五、排列组合排列组合的个数import math # 阶乘 math.factorial(n) # 组合 C(n,k) math.comb(n, k) # 排列 A(n,k) math.perm(n, k)排列itertools.permutations([1,2,3], 2)122113312332组合import itertools lst [10, 20, 30, 40] # 生成所有 3 个数的组合自动满足 ijk for item in itertools.combinations(lst, 3): print(item)(10,20,30) (10,20,40) (10,30,40) (20,30,40)问题描述蓝桥小镇披萨店的老板刚刚烤制了他人生中的第 nn 个披萨为了庆祝这一重要时刻他推出了一项名为 “幸运订单” 的活动顾客有机会赢取免费披萨。以下是活动的具体规则生成订单编号每位顾客需要生成一个九位数的订单编号。生成方法如下首先将数字 11 到 88 进行任意排列 (每个数字正好出现一次)组成一个八位数。然后在这个八位数的任意位置可以是开头、结尾或中间插入一个 11 到 88 的数字从而得到一个九位数的订单编号。计算最大公约数赢取免费披萨披萨店老板会计算每位顾客生成的订单编号与 nn 的最大公约数GCD。如果某个订单编号与 nn 的最大公约数最大那么该顾客就有机会赢得免费披萨。注意订单编号必须严格满足上述生成规则如果有多个订单编号与 nn 的最大公约数相同且达到最大值则只有生成数值最小的订单编号的顾客能够获奖。现在小蓝也想参加这个活动并希望赢取免费披萨。请你帮助小蓝找出能够让他赢得免费披萨的订单编号。输入格式输入一行包含一个八位的正整数 nn表示披萨店老板烤制的第 nn 个披萨。输出格式输出一行包含一个九位的正整数表示答案即小蓝能够赢得免费披萨的最小订单编号。import itertools import math n int(input()) max_gcd 0 best_num 999999999 # 保存答案满足条件的最小数 # 1. 枚举 1~8 的所有 8 位排列不重复 for p in itertools.permutations(12345678): eight .join(p) # 8位数字符串 # 2. 枚举要插入的数字1~8 for insert_d in 12345678: # 3. 枚举插入的位置0~8共9个位置 for pos in range(9): # 插入数字生成 9 位数 nine eight[:pos] insert_d eight[pos:] num int(nine) # 计算当前 gcd current_gcd math.gcd(n, num) # 核心判断 if current_gcd max_gcd: # GCD更大 → 直接更新 max_gcd current_gcd best_num num elif current_gcd max_gcd: # GCD相同 → 保留更小的数 if num best_num: best_num num print(best_num)