质数、因数、最大公约数经典问题整理

1、计数质数

MX = 5000000
is_prime = [1] * MX
is_prime[0] = is_prime[1]= 0
for 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] = Truefor i in range(1, mx + 1):g = 0  # 0 和任何数 x 的最大公约数都是 xfor j in range(i, mx + 1, i):  # 枚举 i 的倍数 jif has[j]:  # 如果 j 在 nums 中g = gcd(g, j)  # 更新最大公约数if g == i:  # 找到一个答案（g 无法继续减小）ans += 1break  # 提前退出循环return ans

 3、子数组的最大 GCD-Sum

利用子数组gcd值为有限个的情况（复杂度为lgn），对每个gcd值使用最大长度数组进行匹配

class Solution:def maxGcdSum(self, nums: List[int], k: int) -> int:maxl = 0pre = [0]for num in nums:pre.append(pre[-1] + num)g = deque()for i, num in enumerate(nums):temp, s, si = deque(), num, iwhile g:n2, j = g.pop()if gcd(n2, s) < s:temp.appendleft((s, si))if i - si + 1 >= k:maxl = max(maxl, (pre[i + 1] - pre[si]) * s)s, si = gcd(n2, s), jelse:si = jelse:temp.appendleft((s, si))if i - si + 1 >= k:maxl = max(maxl, (pre[i + 1] - pre[si]) * s)g = tempreturn 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 ans

4、n 的第 k 个因子

class Solution:def kthFactor(self, n: int, k: int) -> int:count = 0factor = 1while factor * factor <= n:if n % factor == 0:count += 1if count == k:return factorfactor += 1factor -= 1if factor * factor == n:factor -= 1while factor > 0:if n % factor == 0:count += 1if count == k:return n // factorfactor -= 1return -1

5、分解质因数 --  分割数组使乘积互质

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  # 第一次遇到质数 pfor i, x in enumerate(nums):d = 2while d * d <= x:  # 分解质因数if x % d == 0:f(d, i)x //= dwhile x % d == 0:x //= dd += 1if x > 1: f(x, i)max_r = 0for l, r in enumerate(right):if l > max_r:  # 最远可以遇到 max_rreturn max_r  # 也可以写 l-1max_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 = 0for num in nums:res += cnt[k // gcd(k, num)]for num in nums:if num * num % k == 0:res -= 1return res // 2