글 읽기 - 반례를 찾지 못 하겠습니다.

adfsfsf 5년 전 0

빠른 거듭제곱 알고리즘을 검색해서 적용했습니다.

#include <stdio.h>
long long int power(long long int a, long long int b, long long int c);
int main(void)
{
	long long int i, a, b, c, d = 1;
	scanf("%lld %lld %lld", &a, &b, &c);
	a %= c;
	d = power(a, b, c);
	printf("%lld\n", d);
	return 0;
}
long long int power(long long int a, long long int b, long long int c)//거듭제곱 함수
{
	long long int d;
	if (b == 1)
		return a;
	else
	{
		d = power(a, b / 2, c);
		if (b % 2 == 0)
			return (d*d) % c;
		else
			return (d*d*a) % c;
	}
}

k5nen 5년 전 1

d*d*a 처럼 3개의 수를 곱하면 long long int의 범위를 벗어날 수 있습니다.

adfsfsf 5년 전 0

그렇다면 ((d*d)%c)*a)%c를 해야 겠군요. 감사합니다.

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

문제

문제

출처

ICPC

반례를 찾지 못 하겠습니다.

adfsfsf 5년 전 0

k5nen 5년 전 1

adfsfsf 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말