You need to enable JavaScript to run this app. Codechef题解:给定N、M求满足模运算条件的有序对数量及代码优化
优惠活动
大模型
产品
解决方案
定价
更多

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)$计算,无需遍历。

优化思路

  1. 优先计算$b > M$的部分:如果$n > m$,这部分的总对数为$\frac{(m + n -1) \times (n - m)}{2}$,直接累加到结果中
  2. 仅遍历$b$从2到$\min(m, n)$,对每个$b$:
    • 计算$k = m // b$,$V = b \times k$
    • 统计$V$的正约数中小于$b$的数量,累加到结果中
  3. 用一次性读入输入的方式替代逐行读入,进一步提升多组用例的处理速度

优化后代码

通用试除法版本(适合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

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级,最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分), 限时 9.9 元起

最近更新时间:2026.10.21 10:24:02