Codechef 问题给定整数 N 和 M，找出有序对 (a,b) 的数量，使得 1≤a<b≤N 和 ((M mod a) mod b) = ((M mod b) mod a) help plss [英] Codechef problem Given integers N and M, find the number of ordered pairs (a,b) such that 1≤a&lt;b≤N and ((M mod a) mod b) = ((M mod b) mod a) help plss

问题描述

到目前为止我所做的就是这些我正在尝试以更短的时间优化代码.但它不起作用.

this is so far all i have done i am trying to optimize the code for less time.but it is not working.

for _ in range(int(input())):
n, m = map(int, input().split())
count = 0
for i in range(1, n+1):
    for j in range(1, n+1):
        if i < j <= n and ((m%i)%j) == ((m%j)%i):
            count += 1
print(count)

我尝试的另一种方法:

if i < j <= n and (m-(m%j))%i == 0:

两个条件都给出了正确的结果.但显示超出时间限制

both condition give correct result.but show time limit exceed

我该怎么办.谢谢

推荐答案

你的方法是一个好的开始，但需要完全 N * N 次迭代.

Your approach is a good start but takes exactly N * N iterations.

您可以从以下改进开始.

You can start with following improvements.

1. 对数据进行排序

1. sort the data

使用 2 指针方法优化第二个指针的搜索范围

Using 2 pointer approach with optimised search range for second pointer

for i in range(1, n+1):
    for j in range(i+1, n+1): # note j start at `i+1`

这篇关于Codechef 问题给定整数 N 和 M，找出有序对 (a,b) 的数量，使得 1≤a<b≤N 和 ((M mod a) mod b) = ((M mod b) mod a) help plss的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！