algorithm - 互质数取模序列范围的快速算法/公式

Question

在我的项目中，存在一部分问题。但为简化起见，这里提出了问题。有两个互质正整数:a和 b , 其中a < b . a 的倍数从 1 到 b-1由 b 列出后跟模运算.

a mod b , 2*a mod b , 3*a mod b , ... , (b-1)*a mod b

现在，还有另一个整数，比如 n ( 1 <= n < b) .通过第一个n列表中的数字，我们必须找出有多少数字小于m (1 <= m < b)。这可以通过蛮力方法完成，从而给出 O(n) .

一个例子:

a=6, b=13, n=8, m=6

列表是:

6, 12, 5, 11, 4, 10, 3, 9, 2, 8, 1, 7

这是从 1 到 12 的数字排列，因为如果我们包含另一个数字，即 0，则任何两个互素数的模运算都会产生数字排列。 .如果我们取 a= 2, b=13 , 那么列表就是 2, 4, 6, 8, 10, 12, 1, 3, 5, 7, 9, 11 , 这给出了一个模式。而如果 a和 b非常大(在我的项目中它们可以达到 10^20)，那么我不知道如何推断出如此大的数字的模式。

现在回到例子，我们取第一个n = 8列表中的数字，这给出了

6, 12, 5, 11, 4, 10, 3, 9

应用less-than运算符 m = 6 , 它给出的数字总数小于 m如下列表中所述为 3

0, 0, 1, 0, 1, 0, 1, 0

其中 0 表示不小于 m 1 表示小于 m .

因为，上面的算法是一个O(n) ，这对于 [0, 10^20] 的范围是 Not Acceptable ，社区也可以提供提示/线索/提示，使我能够达到 O(log n )解决方案，甚至更好O(1)解决方案？

Answer 1

(警告:我对乘数的范围不是 [0, n] 有点紧张)，所以我调整了它。补偿很容易。)

我将使用经过测试的 Python 代码绘制一个运行时间为 O(log max {a, b}) 的实现。首先，这里有一些实用函数和一个简单的实现。

from fractions import gcd
from random import randrange


def coprime(a, b):
    return gcd(a, b) == 1


def floordiv(a, b):
    return a // b


def ceildiv(a, b):
    return floordiv(a + b - 1, b)


def count1(a, b, n, m):
    assert 1 <= a < b
    assert coprime(a, b)
    assert 0 <= n < b + 1
    assert 0 <= m < b + 1
    return sum(k * a % b < m for k in range(n))

现在，我们如何才能加快速度？第一个改进是将乘数划分为不相交的范围，使得在一个范围内，a 的相应倍数介于 b 的两个倍数之间。知道最低值和最高值后，我们可以通过上限除法计算小于 m 的倍数。

def count2(a, b, n, m):
    assert 1 <= a < b
    assert coprime(a, b)
    assert 0 <= n < b + 1
    assert 0 <= m < b + 1
    count = 0
    first = 0
    while 0 < n:
        count += min(ceildiv(m - first, a), n)
        k = ceildiv(b - first, a)
        n -= k
        first = first + k * a - b
    return count

这还不够快。第二个改进是用递归调用替换大部分 while 循环。在下面的代码中，j 是在存在环绕的意义上“完成”的迭代次数。 term3 使用类似于 count2 的逻辑说明剩余的迭代。

每个完整的迭代在阈值 m 下贡献 floor(m/a) 或 floor(m/a) + 1 个残差.我们是否获得 + 1 取决于该迭代的 first 是什么。 first 从 0 开始，在 while 的每次迭代中以 a - (b % a) modulo a 变化环形。只要它低于某个阈值，我们就会得到 + 1，并且可以通过递归调用计算这个计数。

def count3(a, b, n, m):
    assert 1 <= a < b
    assert coprime(a, b)
    assert 0 <= n < b + 1
    assert 0 <= m < b + 1
    if 1 == a:
        return min(n, m)
    j = floordiv(n * a, b)
    term1 = j * floordiv(m, a)
    term2 = count3(a - b % a, a, j, m % a)
    last = n * a % b
    first = last % a
    term3 = min(ceildiv(m - first, a), (last - first) // a)
    return term1 + term2 + term3

运行时间可以类似于欧几里得 GCD 算法进行分析。

这里有一些测试代码来证明我的正确性声明的证据。请记住在测试性能之前删除断言。

def test(p, f1, f2):
    assert 3 <= p
    for t in range(100):
        while True:
            b = randrange(2, p)
            a = randrange(1, b)
            if coprime(a, b):
                break
        for n in range(b + 1):
            for m in range(b + 1):
                args = (a, b, n, m)
                print(args)
                assert f1(*args) == f2(*args)


if __name__ == '__main__':
    test(25, count1, count2)
    test(25, count1, count3)