이항 계수 모듈로 142857

Question

대용량 이모 트를 계산하는 방법 n 및 r에 대해 142857을 모듈로 계산합니다. 142857에 특별한 것이 있습니까? 문제는 p은 우리가 루카스 정리를 사용할 수 있지만 무엇 142857.

Answer 1

알고리즘에 대해 수행해야 소수 모듈 p 경우입니다 : 주요 능력에 기초 factorise

• ; 142857 = 3^3 × 11 × 13 × 37
• 각 나머지 전력을 모듈로 한 결과를 계산합니다.
• 중국 잉여 정리를 사용하여 결과를 결합합니다.

---

(n above k) mod p^q 계산하려면 :

출처 : http://www.dms.umontreal.ca/~andrew/PDF/BinCoeff.pdf, 정리 한

후 n로 n_j을 정의 p

에 의해 divible되지 않은 번호 1..n의 제품으로 (n!)_p을 정의 소거 j 최하위 디 (가) j 낮은 자리에서 운반 계산하지 k+r 추가시 1로 s 정의베이스 p

에서

운반 수로 e_j 정의 k 컴퓨팅 -베이스 p

에 GITS는 rn로 정의 if p=2 & q>=3 및 -1이면

다음으로 (n above k) mod p^q := p^e_0 * s^e_(q-1) * concatenate(j=d..0)((n_j!)_p/((k_j!)_p*(r_j!)_p))의 결과는 하나의 기본 -p 숫자를 계산하는 연결의 각 용어와 함께 가장 낮은 0이 아닌 숫자를 계산하는 가장 낮은 숫자는 j입니다.

Answer 2

142857의 특별한 점은 7 * 142857 = 999999 = 10^6-1입니다. 이것은 a = 10 및 p = 7 인 Fermat의 Little Theorem에서 발생하는 요소로 모듈 식 등가성을 나타냅니다. 10 (mod 7). 즉, 대부분의 모듈로 999999를 모듈로 사용하고 마지막 모듈러를 7로 나눔으로써 최종 모듈로 줄일 수 있습니다. 이것의 장점은 모듈 분할이 k = 1,2,3,6에 대한 10^k 형식의 표현베이스에서 매우 효율적이라는 것입니다. 이런 경우 모두 숫자 그룹을 합치면됩니다. 이것은 casting out nines의 일반화입니다.

이 최적화는 하드웨어 기반 10 곱셈을 사용하면 실제로 의미가 있습니다. 정말 종이와 연필로해야한다면 잘 작동한다고 말할 수 있습니다. 이 문제는 최근에 온라인 경연 대회에 출현 한 것이므로 그 질문의 근원이라고 생각합니다.

Answer 3

실제로는 C(n,k) % m을 O(n) 시간으로 임의로 계산할 수 있습니다. m.

트릭은 처음부터 나중에 두 빼기, 프라임 파워 벡터로 n!, k! 및 (n-k)!을 계산하고 나머지 모듈 m를 곱하는 것입니다.C(10, 4) 위해 우리는이 작업을 수행 : 어떤 부서가 없기 때문에

10! = 2^8 * 3^4 * 5^2 * 7^1 
4! = 2^3 * 3^1 
6! = 2^4 * 3^2 * 5^1 

는 따라서

C(10,4) = 2^1 * 3^1 * 5^1 * 7^1 

우리는이 쉽게 mod m을 계산할 수 있습니다. 트릭은 선형 시간에 n!과 친구들의 분해를 계산하는 것입니다. 소수점을 n까지 미리 계산하면 다음과 같이 효율적으로 처리 할 수 ​​있습니다. 1*2*...*9*10 제품의 각 짝수에 대해 분명히 2 인수를 얻습니다. 네 번째 숫자마다 두 번째 등을 얻습니다. 따라서 의 수는 n!이고 n/2 + n/4 + n/8 + ...입니다 (여기서 /은 바닥재입니다). 우리는 나머지 소수에 대해서도 똑같은 작업을 수행하며, O(n/logn) 소수는 n보다 작고 각각 O(logn)을 사용하기 때문에 분해가 선형입니다. 이 에라토스테네스의 체를 포함

func Binom(n, k, mod int) int { 
    coef := 1 
    sieve := make([]bool, n+1) 
    for p := 2; p <= n; p++ { 
     if !sieve[p] { 
      // Sieve of Eratosthenes 
      for i := p*p; i <= n; i += p { 
       sieve[i] = true 
      } 
      // Calculate influence of p on coef 
      for pow := p; pow <= n; pow *= p { 
       cnt := n/pow - k/pow - (n-k)/pow 
       for j := 0; j < cnt; j++ { 
        coef *= p 
        coef %= mod 
       } 
      } 
     } 
    } 
    return coef 
} 

때문에 소수가 미리 계산 또는 빠른 체로 체질 된 경우 실행 시간은 nloglogn보다는 n입니다 :

실제로

다음과 같이 나는 더 암시 코드 것 .