이 두 숫자 <code>N</code> 및 <code>p</code>을 감안할 때 N

일부 번호 서로 소 모듈로, k이 p^k가 N! 분할 p 있도록의 최대 전력하고 d = N!/(p^k)을 할 수 있습니다. 따라서 d 및 p은 다른 경우입니다.이 두 숫자 <code>N</code> 및 <code>p</code>을 감안할 때 N

어떻게 찾을 수 있습니까? d mod p? N이 높을 때 N!이 매우 높기 때문에 직접 반복은 실용적이지 않습니다. 표현을 찾으려면보다 효율적인 알고리즘이 필요합니다. 여기

'p' 프라임이라고 부탁해도 될까요? –

나는 이것을위한 효율적인 일반적인 알고리즘이있을 것이라고 생각하지 않는다. 'p> N'의 경우를 고려해보십시오.'d (= N!) mod p '를 찾기 위해'N '곱셈보다 더 잘할 수 없습니다. – us2012

또한 'p'의 크기에는 제한이 있습니까? –

은 O (N) 알고리즘 :

int d=1; 
for(int i=1;i<=N;++i) 
{ 
    d*=i; 
    while(d%p==0) 
     d/=p; 
    d=d%p; 
}

그것은 큰 숫자를 저장 요구하지 않기 때문에, 허용 될 수있다. 나는 O (p) 알고리즘이 가능하다고 의심한다. 왜냐하면 (매 k * p 후에 숫자가 반복 될 것이기 때문이다.) 그러나 코드는 좀 더 복잡 할 것이다.

2013-03-09 11:04:05 maxim1000

답변