모듈러 산술을위한 코드 최적화

큰 수의 경우 아래 표현식을 계산하려고합니다. 이 식의 값이 매우 큰 것 때문에 모듈러 산술을위한 코드 최적화

N!/((N/2)!(N/2)!)

은, 난 그냥이 식의 값이 일부 소수를 계수해야합니다. 이 표현식의 값이 x이고 소수 1000000007을 선택한다고 가정합니다. 나는 x % 1000000007을 찾고 있습니다.

여기 내 코드입니다.

#include<iostream> 
#define MOD 1000000007 
using namespace std; 
int main() 
{ 
    unsigned long long A[1001]; 
    A[2]=2; 
    for(int i=4;i<=1000;i+=2) 
    { 
     A[i]=((4*A[i-2])/i)%MOD; 
     A[i]=(A[i]*(i-1))%MOD; 

    while(1) 
    { 
     int N; 
     cin>>N; 
     cout<<A[N]; 
    } 
}

하지만 N이 50 인 경우에도,이 최적화는 많은 예를 들면 N. 큰 값 실패 올바른 출력 605552882이지만,이 날 132924730 제공

. 올바른 출력을 얻으려면 어떻게 최적화 할 수 있습니까?

참고 : N을 짝수로만 간주합니다.

출처

2013-02-06 g4ur4v

도움이되기를 바랍니다. – g4ur4v

[n을 계산하는 빠른 방법! mod m 여기서 m은 소수입니다.] (http://stackoverflow.com/questions/9727962/fast-way-to-calculate-n-mod-m-where-m-is-prime). 또한 이것은 더 잘 맞지만 답이 없습니다 : [큰 프라임 p와 매우 큰 N에 대해 nCk % P를 계산하는 방법] (http://stackoverflow.com/questions/14475139) –

모듈러 산술을 할 때 나눗셈과 같은 연산은 없습니다. 대신에 분모의 모듈화 된 역수를 취해 곱합니다. 모듈러 역변환 1779 에티엔 베주 발견 확장 유클리드 알고리즘을 사용하여 계산된다

# return y such that x * y == 1 (mod m) 
function inverse(x, m) 
    a, b, u := 0, m, 1 
    while x > 0 
     q, r := divide(b, x) 
     x, a, b, u := b % x, u, x, a - q * u 
    if b == 1 return a % m 
    error "must be coprime"

divide 함수는 몫과 나머지 모두를 리턴한다. 위에 주어진 할당 연산자는 모두 동시 할당입니다. 여기에서 모든 오른쪽이 먼저 계산 된 다음 모든 왼쪽이 동시에 할당됩니다. 모듈러 산술에 대한 자세한 내용은 my blog에서 확인할 수 있습니다. 다음

더 모듈러스 나눗셈이 전혀 필요하지 않다 우선

출처

2013-02-06 19:13:28 user448810

이 수식은 rewrited 될 수있다! (! (N/2)^2)

N/= (1.2.3 을 .. (N/2 + 1) ... N)/(1.2.3 ... N/2) * (1.2.3 ... N/2) 이제 작은
에 의해 더 큰 수를 분할하는 ..N/2))
- 확인은 그래서 당신은 제수와 divident
- 그래서 부스 하위 결과이 당신이에서와 (/ 2 N)로하는 경우
- 오버 플로우하지 않도록합니다 비슷한 크기를
- 모두 숫자들을
- 를 왼쪽으로 이동 2 나눌 수있는 모든 시간을! 나머지에 대해서만 곱셈을 계속하는 것보다. 이 후 1
- 에 의해 divison 왼쪽 때까지
- 모두 subresults 아무것도에 의해 나눌 수있는 모든 시간은 normaly 끝까지 모듈로를 arithmetics에 거는 수 있습니다 그들에게
- 를 나눕니다.
더 많은 고급 접근 방식을 보려면 여기를 참조하십시오.
- N! 및 (N/2)!여기
- 내가 뭘 찾았는지입니다 당분간, ... 그것은 내가 해결했다
- 첫 모습에서 보이는 것보다 훨씬 더 분해 있습니다 : 바로 가기에 Fast exact bigint factorial
- 검색어 N은! ((N/2)!)^2가 완전히 사라집니다.
- 단순한 프라임 분해 + 4N < -> 1N 보정

솔루션을 생각 나게합니다 :

I. (4N!)=((2N!)^2) . mul(i=all primes<=4N) of [i^sum(j=1,2,3,4,5,...4N>=i^j) of [(4N/(i^j))%2]] 
II. (4N)!/((4N/2)!^2) = (4N)!/((2N)!^2) 
---------------------------------------- 
I.=II. (4N)!/((2N)!^2)=mul(i=all primes<=4N) of [i^sum(j=1,2,3,4,5,...4N>=i^j) of [(4N/(i^j))%2]]

유일한 것은 N은 4로 나눌 수 있어야한다는 것입니다 ... 그러므로 모든면에서 4N입니다.
N-N % 4에 대해 N % 4! = 0을 풀 때와 그 결과가 잘못된 1-3의 수로 수정 된 경우.

이 code.I'll 대신 다른 공식을 사용하여 시도 개선하기 위해 할 수있는 많은 것이없는 것 같습니다 답변에 따라 경찰이

출처

2013-09-03 14:31:39 Spektre

모듈러 산술을위한 코드 최적화

답변

관련 문제