Codechef题解:给定N、M求满足模运算条件的有序对数量及代码优化
问题分析与优化方案
原代码超时原因
你最初的实现时间复杂度为$O(n^2)$,当$n$超过1000时运算量就会达到百万级,规模更大时必然触发时间超限,必须通过数学推导降低复杂度。
数学推导简化条件
我们可以对原等式做等价转换:
- 因为约束为$a < b$,所以$M \mod a < a < b$,因此左侧$(M \mod a) \mod b = M \mod a$
- 原等式简化为$M \mod a = (M \mod b) \mod a$
- 代入$M \mod b = M - b \times \lfloor M / b \rfloor$,进一步推导可得等价条件:$(b \times \lfloor M/b \rfloor) \mod a = 0$
- 特殊情况:当$b > M$时,$\lfloor M/b \rfloor = 0$,此时条件对所有$a < b$都成立,这部分可以直接用等差数列求和公式$O(1)$计算,无需遍历。
优化思路
- 优先计算$b > M$的部分:如果$n > m$,这部分的总对数为$\frac{(m + n -1) \times (n - m)}{2}$,直接累加到结果中
- 仅遍历$b$从2到$\min(m, n)$,对每个$b$:
- 计算$k = m // b$,$V = b \times k$
- 统计$V$的正约数中小于$b$的数量,累加到结果中
- 用一次性读入输入的方式替代逐行读入,进一步提升多组用例的处理速度
优化后代码
通用试除法版本(适合M≤1e5的场景)
import sys import math def count_div_less(V, limit): res = 0 sqrt_v = int(math.isqrt(V)) for i in range(1, sqrt_v + 1): if V % i == 0: if i < limit: res += 1 other = V // i if other != i and other < limit: res += 1 return res def main(): input = sys.stdin.read data = input().split() t = int(data[0]) idx = 1 for _ in range(t): n = int(data[idx]) m = int(data[idx+1]) idx += 2 ans = 0 # 处理b>m的情况 if n > m: cnt_b = n - m first = m last = n - 1 ans += (first + last) * cnt_b // 2 upper_b = min(m, n) if upper_b < 2: print(ans) continue for b in range(2, upper_b + 1): k = m // b V = b * k ans += count_div_less(V, b) print(ans) if __name__ == "__main__": main()
预处理约数版本(适合M≤1e6的场景,速度更快)
import sys import bisect # 提前预处理1e6以内所有数的约数列表 MAX = 10**6 + 5 divisors = [[] for _ in range(MAX)] for i in range(1, MAX): for j in range(i, MAX, i): divisors[j].append(i) def main(): input = sys.stdin.read data = input().split() t = int(data[0]) idx = 1 for _ in range(t): n = int(data[idx]) m = int(data[idx+1]) idx += 2 ans = 0 if n > m: cnt_b = n - m first = m last = n - 1 ans += (first + last) * cnt_b // 2 upper_b = min(m, n) if upper_b < 2: print(ans) continue for b in range(2, upper_b + 1): k = m // b V = b * k # 二分查找小于b的约数个数 cnt = bisect.bisect_left(divisors[V], b) ans += cnt print(ans) if __name__ == "__main__": main()
内容的提问来源于stack exchange,提问作者Arshad Hossain
相关产品推荐
相关产品推荐

