글 읽기 - 거듭제곱 계산 코드 질문요 ㅠ

p_ce1052 8달 전 0

b^num 제곱을 log num 만에 계산하는 알고리즘을 구현했는데 무한반복됩니다. 왜 계속 똑같은 함수를 호출하는지 모르겠습니다 값을 리턴했는데도요. 여기서 num으로 사용되는 수는 1,000,000,005 입니다.

long long f(long long b,long long num){
	cout<<b<<" "<<num<<'\n';
	if(num==1) return b;
	if(num%2){//홀수인경우   
		return (((f(b,num/2)*f(b,num/2))%p)*b)%p;
	}
	else{//짝수인경우  
		return (f(b,num/2)*f(b,num/2))%p;
	}
}

pentagon03 8달 전 0

1. num=0 이 들어오는 경우 무한 반복됩니다.

2. 리턴할 때 중복 호출이 발생합니다. 변수를 하나 잡아 값을 저장해놓고 계산하시면 됩니다.

=> int k= f(b,num/2); return k*k%p;

p_ce1052 8달 전 0

감사합니다 2번 처럼 고치니까 바로 해결되었네요 bb

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

거듭제곱 계산 코드 질문요 ㅠ

p_ce1052 8달 전 0

pentagon03 8달 전 0

p_ce1052 8달 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말