공동 소수 (co-prime number)의 모듈러의 직렬 범위에 대한 빠른 알고리즘/공식

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까지 갈 수 있음), 그런 많은 수의 패턴을 추론하는 방법을 모릅니다.

는

지금 예제로 되돌아지고, 우리가 m = 6으로 less-than 연산자를 적용

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

을 제공하는 목록에서 첫 번째 n = 8 번호를 가지고 , 그것은 m 것보다 적은 수의 총 수를 제공 (3) 같은리스트에 대해서 설명 0 지칭

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

m보다 작지 않고 1은 m보다 작음을 나타냅니다. 이후

은 위의 알고리즘은 [0, 10^20]의 범위에 사용할 수없는, 그래서 지역 사회가 O(log n) 솔루션, 또는 더 나은 O(1) 솔루션에 도달하는 저를 가능하게하기위한 힌트/힌트/팁을 줄 수있는하는 O(n)입니까?

Answer 1

(경고 : [0, n]이 아닌 배율기 범위에 대해 약간의 트릭이있어, 조정했습니다.

테스트 한 파이썬 코드를 사용하여 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 루프를 재귀 호출로 대체하는 것입니다. 아래의 코드에서 ""은 랩 어라운드라는 의미에서 "완료"되는 반복 횟수입니다. 은 count2과 유사한 논리를 사용하여 나머지 반복을 설명합니다.

각 반복의 각각은 m 임계 값 아래에 floor(m/a) 또는 floor(m/a) + 1 잔여 물을 제공합니다. 우리가 + 1을 얻는 지 여부는 그 반복을 위해 무엇이 first인지에 달려 있습니다. first은 0에서 시작하고 while 루프를 통해 각 반복마다 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 

실행 시간은 Euclidean 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)