CCF CSP认证 20231202 因子化简 满分题解 + 标准题解 Python实现

因子化简

一、概述

  本题目结合素数求解，按特定幂次要求，对整数进行因子分解，考察常见算法（素数求解）、降低时间复杂度的方法，难度简单。真题跳转官网查看。
 真题来源： 因子化简
 官网地址：www.cspro.org(模拟考试入口)

二、题目分析

  输入 q 组整数 ni n_ini​和权重 ki k_iki​，i=1,2,…,q；求每组整数的素数因子 p1, p2, . . . , pm p_1,p_2,…,p_mp1​,p2​,…,pm​，使该整数按素数幂的积表示，即 n = p1 t 1× p2 t 2× . . . × pm t m n = p_1^{t_1} \times p_2^{t_2} \times … \times p_m^{t_m}n=p1t1​​×p2t2​​×…×pmtm​​；将整数依照每组的权重 ki k_iki​，剔除幂 < ki <k_i<ki​的素数因子；输出剩余项的乘积，若无剩余项则输出1。

三、满分题解

1. 题解一（就题解题）

• 第一步，接受一个正整数，它表示查询个数 q 。接受 q 组输入。每组输入包含正整数 n 和 k ，n 为要查询的整数，k 为权重。时间复杂度为$O(n)$。
• 第二步，求素数因子，需要判断一个数是否为素数。首先明白概念，素数，指的是在大于1的自然数中，除了1和它本身以外不再有其他因数的数。换句话说，素数是只有两个正因数（1和自身）的自然数。 定义 函数is_prime(num) ，接受参数 num ，是素数返回 True ，否则返回 False 。当接受的参数$num\le 1$，则一定不是素数；当$num==2$，一定是素数；对于其他数：如果一个数不是素数，那么它一定能被它的某个因数整除，而这个因数又不大于它的平方根。所以，因数检查到平方根就可以了。只需要写个循环，若 num 能被因数 i 整除，则 num 不是素数，返回 False 。若 [2,num平方根] 检查结束， num 也未被某个因数整除，则 num 是素数，返回 True 。时间复杂度为O( n)O(\sqrt n) O(n ​)
• 第三步，求 n 的素数因子及各素数因子的幂。由题子任务的描述可知1<n≤1 0 101<n \leq 10^{10} 1<n≤1010，并且最终简化后若无剩余项则输出1。每一个合数（非素数）都可以唯一地表示为有限个素数的乘积，若有一素数>1 0 510^{5} 105，那该素数的倍数也会>1 0 1010^{10} 1010。并且，k>1，因此，直接求10000以内的素数因子。根据数学运算法则，按素数因子从小到大依次求素数因子的指数，剔除非因子的素数。得到包含素数因子：因子对应的指数的字典。函数prime_item(num)，时间复杂度为999998×O( n)+O(max(幂次)n)+2O(n)999998\times O(\sqrt n)+O(max(幂次)n) + 2O(n) 999998×O(n ​)+O(max(幂次)n)+2O(n)
• 第四步，因子简化，计算输出值。定义计算初始值mlc 为1，遍历素数因子键值对，若值>=k，则mcl累乘幂指数即可。时间复杂度为$O(n)$
• 第五步，格式化输出。输出mlc，时间复杂度为$O(1)$。

1.1 编码实现

def is_prime(num):# 判断是否为素数if num <= 1:return Falseif num == 2:return Truefor i in range(2, int(num ** 0.5)+1):if num % i == 0:return Falsereturn Truedef prime_item(num):# 求素数因子：因子对应的指数# 求 2到sqrt(10**10)的素数因子prime_li = []prime_dic = {}for i in range(2, 100000): # 因子if is_prime(i):prime_dic[i] = 0prime_li.append(i)# 求素数因子的指数for prime in prime_li:while num % prime == 0:prime_dic[prime] += 1num = num / primeif num == 1:break# 处理非因子的素数del_key = []for key in prime_dic.keys():if prime_dic[key] == 0:del_key.append(key)for key in del_key:del prime_dic[key]return prime_dicif __name__ == "__main__":q = int(input())# 查询个数for i in range(q):mlc = 1 # 乘积结果n, k = map(int, input().split())# n:整数 k:阈值primes = prime_item(n)for item in primes.items():if item[1] >= k:mlc *= item[0]**item[1]print(mlc)

1.2 提交结果

1.3 优化题解一

  在题解一中，prime_item(num) 函数执行了 q 次，所以求 2 → 1 05 2 \rightarrow 10^{5}2→105的素数因子也执行了 q 次，实际上只需一次生成 prime_li 即可。

1.3.1 编码实现

def is_prime(num):# 判断是否为素数if num <= 1:return Falseif num == 2:return Truefor i in range(2, int(num ** 0.5)+1):if num % i == 0:return Falsereturn Truedef get_prime_li(): # 求2到sqrt(10**10)的素数因子prime_li = []for i in range(2, 100000): # 因子if is_prime(i):prime_li.append(i)return prime_lidef get_prime_dic(num, prime_li):# 求素数因子：因子对应的指数prime_dic = {}for p in prime_li: # 初始化prime_dic[p] = 0# 求素数因子的指数for prime in prime_li:while num % prime == 0:prime_dic[prime] += 1num = num / primeif num == 1:break# 处理非因子的素数del_key = []for key in prime_dic.keys():if prime_dic[key] == 0:del_key.append(key)for key in del_key:del prime_dic[key]return prime_dicif __name__ == "__main__":q = int(input())# 查询个数prime_li = get_prime_li()for i in range(q):mlc = 1 # 乘积结果n, k = map(int, input().split())# n:整数 k:阈值primes = get_prime_dic(n, prime_li)for item in primes.items():if item[1] >= k:mlc *= item[0]**item[1]print(mlc)

1.3.2 提交结果

2. 题解二（通解）

  可将本题看作是三个问题。问题一：判断整数n是否为素数；问题二：求整数n以内的所有素数；问题三：求n的因子分解形式，素数因子的乘积。

• 问题一：由于因子总是程度出现的。例如： $n\%a\equiv 0\iff n\equiv a\ast b$ 则有 m i n ( a , b ) ≤ n≤ m a x ( a , b )min(a,b) \leq \sqrt n \leq max(a,b)min(a,b)≤n ​≤max(a,b) 。因此只需检查 [2 , n ][\ 2,\sqrt n \ ][2,n ​] 内是否有 n 的因子即可，若有，则 n 不是素数返回 False ；无，则 n 是素数，返回 True 。时间复杂度为 O ( n)O(\sqrt n)O(n ​)

  def is_prime(num):# 判断num是否为素数for i in range(2, int(num ** 0.5)+1):if num % i == 0:return Falsereturn True

• 问题二：利用埃拉托斯特尼筛法，对于任意大于1的自然数**x,kx(k>1)**是合数。由于因数因数是成对存在的，所以只需要筛选出所有 12n u m{1 \over 2} num21​num以内的素数。时间复杂度为 O ( 12n n)O({1 \over 2}n\sqrt n)O(21​nn ​)

  def get_primes(num): # 素数筛选算法，求num折半以内的所有素数prime_li = [True] * (num + 1) # 初始化：设0-num所有数为素数for i in range(2, num//2 + 1): # 对任意大于1的整数i，ji(j>1)是合数for j in range(2, num//i + 1): # 筛除i的倍数prime_li[j * i] = Falsereturn prime_li

• 问题三：求 n 的因子分解形式。结合问题二求素因子考虑，无需求出 n 所有的素因子，将 ≤ n \leq \sqrt n≤n ​的素因子除去，剩余项 = 1即可。利用元组存储**(素因子，幂)。具体执行时，利用埃拉托斯特尼筛法，在找到一个整数 n 的因子 i 后，将 i 从 n 中除去，保证每个 i 都是素因子**，除法执行的次数就是幂次。时间复杂度为 O ( n)O(\sqrt n)O(n ​)。

  def decompose(num): # 将整数num用因子形式表示 (因子，幂)ans = []i = 2while i * i <= num: # 检查2-sqrt(n)tmp = 0while num % i == 0: # 素数筛选算法, 筛掉i的倍数，每筛一次，i的幂次+1tmp += 1num //= iif tmp > 0:ans.append((i, tmp))i += 1if num > 1: # 大于sqrt(n)的素因子最多只有1个ans.append((num, 1))return ans

2.1 编码实现

def decompose(num): # 将整数num用因子形式表示 (因子，幂)ans = []i = 2while i * i <= num: # 检查2-sqrt(n)tmp = 0while num % i == 0: # 素数筛选算法, 筛掉i的倍数，每筛一次，i的幂次+1tmp += 1num //= iif tmp > 0:ans.append((i, tmp))i += 1if num > 1: # 大于sqrt(n)的素因子最多只有1个ans.append((num, 1))return ansif __name__ == "__main__":q = int(input())# 查询个数for i in range(q):mlc = 1 # 乘积结果n, k = map(int, input().split())# n:整数 k:阈值num_primes = decompose(n)# 求n以内的所有素数因子，并用因子形式表示for item in num_primes:if item[1] >= k:mlc *= item[0]**item[1]print(mlc)

2.2 提交结果

四、小结

  第32、31、30届CSP的第二题，更倾向于基础数学知识应用方面的模拟，对降低时间复杂度以及对子任务及其条件理解程度的考察。本题目若能够合理利用 1<k 这个条件，结合每一个合数（非素数）都可以唯一地表示为有限个素数的乘积这个定理，题解的确会有效降低时间复杂度；若还知道埃拉托斯特尼筛法，the Sieve of Eratosthenes algorithm（ 素数筛选算法 ），那本题就特别简单了。

  上述题解的时间复杂度如下：

• O标准题解= O ( n ) × [ O ( m a x ( 幂次 ) n) + O ( 1 ) ) ≈ O ( n n)O_{标准题解} = O(n) \times [O(max(幂次)\sqrt n) + O(1)) \approx O(n \sqrt n)O标准题解​=O(n)×[O(max(幂次)n ​)+O(1))≈O(nn ​)

• O题解一优化= O ( n ) × { O ( n) + O [ m a x ( 幂次 ) n ] + O ( 1 ) } ≈ O ( n2)O_{题解一优化} = O(n) \times \{O(\sqrt n)+O[max(幂次)n]+O(1)\} \approx O(n^2)O题解一优化​=O(n)×{O(n ​)+O[max(幂次)n]+O(1)}≈O(n2)

• O题解一= O ( n ) × { 999998 × O ( n) + O [ m a x ( 幂次 ) n ] + 2 O ( n ) + O ( 1 ) } ≈ m a x { 999998 × O ( n n) , [ m a x ( 幂次 ) + 2 ] × O ( n2) }O_{题解一} = O(n) \times \{999998\times O(\sqrt n)+O[max(幂次)n] + 2O(n) + O(1)\} \approx max\{999998 \times O(n \sqrt n),[max(幂次)+2] \times O(n^2)\}O题解一​=O(n)×{999998×O(n ​)+O[max(幂次)n]+2O(n)+O(1)}≈max{999998×O(nn ​),[max(幂次)+2]×O(n2)}