글 읽기 - 제곱함수 틀린부분?

dmswl022329 2년 전 0

pow가 느려서 분할정복으로 코드를 짰는데

재귀로 만든 제곱함수를 쓰니 틀렸습니다 라고 나옵니다.

혹시 틀린부분이 어딘지 알 수 있을까요?

long long power(long long x, long long y){
	if(y == 0) return 1;
	else if(y % 2 == 0) return power((x*x)%P, y/2) % P;
	else return ((x % P) * (power(x, y - 1) % P)) % P;
}

lcr7324 2년 전 0

x*x는 long long 범위를 초과할 수 있습니다.

(y가 2의 거듭제곱꼴인 경우를 생각해보세요.)

dmswl022329 2년 전 0

아 그런문제가 있을 수 있군요

한번 고쳐보겠습니다!

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

문제

문제

출처

ICPC

제곱함수 틀린부분?

dmswl022329 2년 전 0

lcr7324 2년 전 0

dmswl022329 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말