Codechef 问题给定整数 N 和 M，找出满足 1≤a<b≤N 和 ((M mod a) mod b) = ((M mod b) mod a) 请帮忙

Question

这就是我到目前为止所做的一切我正在尝试优化代码以减少 time.but 它不起作用。

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:

两个条件都正确result.but显示时间限制超过

我应该怎么办 do.thanks

Answer 1

您的方法是一个好的开始，但正好需要 N * N 次迭代。

您可以从以下改进着手。

对数据进行排序
使用 2 指针方法优化第二个指针的搜索范围

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

Answer 2

由于a < b，我们推断(Mmoda)modb=Mmoda，所以条件等价于Mmoda = (M mod b) mod a，即M − (M mod b)是a的倍数。我们可以使用筛子遍历所有 b 并计算 M − (M mod b) 的因子，从而得到 Θ(N + M log N) 时间算法。

N = 2304
M = 23498


def fast():
    npairs = 0
    nfactors = [1] * (M + 1)
    for b in range(2, N + 1):
        npairs += nfactors[M - M % b]
        for i in range(0, M + 1, b):
            nfactors[i] += 1
    return npairs


def naive():
    return sum((M % a) % b == (M % b) % a for b in range(2, N + 1) for a in range(1, b))


print(fast(), naive())

Answer 3

想像 x%mod(a) 与 x%mod(b) 相同，只有条件 a

(n-1) 适用于所有 1 对

for _ in range(int(input())): n,m=map(int,input().split()) count=0 dictitems=defaultdict(int) for i in range(2,n+1): rem=m%i count+=dictitems[rem] for j in range(rem,n+1,i): dictitems[j]+=1 print(count+(n-1))

Codechef 问题给定整数 N 和 M，找出满足 1≤a<b≤N 和 ((M mod a) mod b) = ((M mod b) mod a) 请帮忙

Codechef problem Given integers N and M, find the number of ordered pairs (a,b) such that 1≤a<b≤N and ((M mod a) mod b) = ((M mod b) mod a) help plss

python

algorithm

modular-arithmetic