나는 (2^n) % p를 찾을 것을 요청하는 질문에 갇혔다. n은 10^36의 매우 큰 숫자이고 p는 소수이다. 어떻게 빨리 이것을 할 수 있는가? 여기 ^는 힘을 의미한다. 나는이 알고리즘을 통해 들어 왔지만 10^(36)가 다른 방법이나 이에 대한 개선이(2^n) % p의 결과를 찾는 방법은 무엇입니까?
double power(double a,double b,int mod)
{
if (b==0)
return 1;
else if(b%2==0)
return square(power(a,b/2,mod))%mod;
else return power(a,b-1,mod)%mod;
}
가 매우 큰로서 스택 오버 플로우를 제공 ??
이 경우 파이썬는 당신을 도울 수 있습니다. 파이썬에서는 데이터 유형의 범위에주의를 기울일 필요가 없습니다. 데이터 값을 제공하면 파이썬은 변수의 데이터 유형을 자동으로 조정합니다.
나누기 및 정복 방식을 사용할 수 있습니다.
2^8 = (2^4)^2 2^4 = (2^2) 따라서^2
, 당신이 2를 계산해야합니다^: 여기
기본적인 생각이다 2를 한 번 정사각형으로 정하면 2^4가됩니다. 그 다음 Square는 2^8을 얻습니다.시연 된 사례는 n이 2의 거듭 제곱 인 경우 완벽하게 작동합니다. 그러나 이와 같은 능력을 2 ~ 3 개의 하위 문제로 나눌 수 있습니다.
예를 들어, n = 20이면 (2^10)^2로 나뉩니다. n = 21이면 (2^10)^2 * 2가됩니다.
따라서 전원의 홀수 및 짝수 값에 따라 구성 요소에 해체 할 수 있습니다.
그림이 분명하길 바랍니다.
OP에 google에 대한 키워드가 필요한 경우 반복 제곱에 의한 지수 계산으로도 알려져 있습니다. –
그래,하지만 10^36이 매우 높다는 것과 재귀 프로 시저에서 스택 오버 플로우가 발생한다는 것을 알고있다. – codeKNIGHT
@ user1020998 : 동일한 방식으로 비 반복적으로 구현할 수 있습니다. 그러나, 그것은 두 배의 힘이고 p는 소수 일 수 있습니다. 아마 어떤 종류의 수학적 트릭이있을 수 있습니다. 그러나 나는 현재 어떤 것도 알지 못합니다. –
어디서 붙어 있었습니까? – Ulterior