质数、因数、最大公约数经典问题整理
1、计数质数
MX = 5000000is_prime = [1] * MXis_prime[0] = is_prime[1]= 0for i in range(2, MX): if is_prime[i]: for j in range(i * i, MX, i): is_prime[j] = 0class Solution: def countPrimes(self, n: int) -> int: return sum(is_prime[:n])2、序列中不同最大公约数的数目
class Solution: def countDifferentSubsequenceGCDs(self, nums: List[int]) -> int: ans, mx = 0, max(nums) has = [False] * (mx + 1) for x in nums: has[x] = True for i in range(1, mx + 1): g = 0 # 0 和任何数 x 的最大公约数都是 x for j in range(i, mx + 1, i): # 枚举 i 的倍数 j if has[j]: # 如果 j 在 nums 中 g = gcd(g, j) # 更新最大公约数 if g == i: # 找到一个答案（g 无法继续减小） ans += 1 break # 提前退出循环 return ans3、子数组的最大 GCD-Sum
利用子数组gcd值为有限个的情况（复杂度为lgn），对每个gcd值使用最大长度数组进行匹配
class Solution: def maxGcdSum(self, nums: List[int], k: int) -> int: maxl = 0 pre = [0] for num in nums: pre.append(pre[-1] + num) g = deque() for i, num in enumerate(nums): temp, s, si = deque(), num, i while g: n2, j = g.pop() if gcd(n2, s) = k: maxl = max(maxl, (pre[i + 1] - pre[si]) * s) s, si = gcd(n2, s), j else: si = j else: temp.appendleft((s, si)) if i - si + 1 >= k: maxl = max(maxl, (pre[i + 1] - pre[si]) * s) g = temp return maxl找到最接近目标值的函数值 与上述做法类似，利用子数组与运算结果为有限个（lgn）的性质，代码如下：
class Solution: def closestToTarget(self, arr: List[int], target: int) -> int: ans = abs(arr[0] - target) valid = {arr[0]} for num in arr: valid = {x & num for x in valid} | {num} ans = min(ans, min(abs(x - target) for x in valid)) return ans4、n 的第 k 个因子
class Solution: def kthFactor(self, n: int, k: int) -> int: count = 0 factor = 1 while factor * factor 0: if n % factor == 0: count += 1 if count == k: return n // factor factor -= 1 return -15、分解质因数 -- 分割数组使乘积互质
class Solution: def findValidSplit(self, nums: List[int]) -> int: left = {} # left[p] 表示质数 p 首次出现的下标 right = [0] * len(nums) # right[i] 表示左端点为 i 的区间的右端点的最大值 def f(p: int, i: int) -> None: if p in left: right[left[p]] = i # 记录左端点 l 对应的右端点的最大值 else: left[p] = i # 第一次遇到质数 p for i, x in enumerate(nums): d = 2 while d * d 1: f(x, i) max_r = 0 for l, r in enumerate(right): if l > max_r: # 最远可以遇到 max_r return max_r # 也可以写 l-1 max_r = max(max_r, r) return -1使用前缀和 -- 向下取整数对和、 统计美丽子字符串 II
6、统计可以被 K 整除的下标对数目
class Solution: def countPairs(self, nums: List[int], k: int) -> int: mx = max(max(nums), k) cnt = [0] * (mx + 1) for num in nums: cnt[num] += 1 #统计每个数的倍数出现的次数 for i in range(1, mx + 1): for j in range(2 * i, mx + 1, i): cnt[i] += cnt[j] res = 0 for num in nums: res += cnt[k // gcd(k, num)] for num in nums: if num * num % k == 0: res -= 1 return res // 2
