在我的项目中,存在一部分问题。但为简化起见,这里提出了问题。有两个互质正整数: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)
解决方案?
最佳答案
(警告:我对乘数的范围不是 [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)
关于algorithm - 互质数取模序列范围的快速算法/公式,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/25829814/