共素数模的串行范围的快速算法/公式

Question

在我的项目中,问题的一部分就在那里.但为了简化,这里的问题正在制定中.有两个正的共素整数:a和b,其中a < b.列出a从1到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,它给出的总数小于m3,如下面列表中所述

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

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

因为上面的算法是a O(n),这对于范围是不可接受的[0, 10^20],所以社区能给出提示/线索/提示以使我能够达到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。

每个完整迭代的贡献floor(m / a)或floor(m / a) + 1残差均低于阈值m。我们是否得到+ 1取决于first该迭代的内容。first开始于并在 while 循环的每次迭代中按模0变化。每当它低于某个阈值时，我们就会得到，并且该计数可以通过递归调用来计算。a - (b % a)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)