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