6

在我的项目中，存在一部分问题。但为了简化起见，这里的问题正在制定。有两个正互质整数：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如下面的列表中所述

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

其中 0 表示不小于m1 表示小于m。

既然，上面的算法是 a O(n)，在 的范围内是不可接受的[0, 10^20]，那么社区可以给一个提示/线索/提示，让我找到一个O(log n )解决方案，甚至更好的O(1)解决方案吗？

4

1 回答 1

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)或残差。我们是否得到取决于该迭代的内容。通过while循环在每次迭代中开始并以模数变化。只要它低于某个阈值，我们就会得到，并且这个计数可以通过递归调用来计算。floor(m / a) + 1m+ 1firstfirst0a - (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)
于 2014-09-15T21:59:36.030 回答