글 읽기 - [C++] 재귀 초보입니다. 어디가 문제인지 여쭤보고 싶습니다.

ghkd3778 6년 전 0

1629번 곱셈 문제입니다.

b가 0일때는 1을, b가 홀수일 때는 1을 줄여서 다시 재귀호출을, 짝수일땐 값을 구해 제곱시켜 리턴시켜주겠다는 생각으로 코드를 짰습니다.

머리로 몇몇 케이스를 생각해 돌려봤을 때는 문제가 없었는데, 어느 부분에서 문제가 나는 걸지 제 머리만으로는 어떻게 찾아야할지 모르겠어서 여러분들의 고견을 듣고자 올립니다.

답변 부탁드립니다. 읽어주셔서 감사합니다.

#include<cstdio>
long long mul(long long a, long long b, long long c);
int main()
{
	long long a, b, c;
	scanf("%lld %lld %lld", &a, &b, &c);
	printf("%lld", mul(a%c, b%c, c));
}
long long mul(long long a, long long b, long long c)
{
	long long ret;
	if (b == 0)
		return 1;
	else if (b % 2 == 1)
		return (a*mul(a%c, (b - 1) % c, c)) % c;
	else
	{
		ret = mul(a%c, (b / 2) % c, c) % c;
		return (ret*ret)%c;
	}
}

jh05013 6년 전 1

a의 c제곱을 c로 나눈 나머지는 1이 아니기 때문에 b는 c로 나누면 안 됩니다.

ghkd3778 6년 전 0

감사합니다!

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

문제

문제

출처

ICPC

[C++] 재귀 초보입니다. 어디가 문제인지 여쭤보고 싶습니다.

ghkd3778 6년 전 0

jh05013 6년 전 1

ghkd3778 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말