글 읽기 - 1629 곱셈 질문 하나

dolmul5000 5년 전 1

짝수에 대한 경우와 홀수에 대한 처리가 조금 다른 것은 인식했습니다.

a^11 = (a^5)^2 * a

a^10 = (a^5)^2

그런데 중간중간 % c 를 하여도 답에는 아무 이상이 없나요 ?

간단한 예시를 들어서 설명해주시면 감사하겠습니다.

#include<iostream>
using namespace std;
long long a, b, c;

long long result(long long x, long long y)
{
	if (y == 0)
		return 1;
	long long k = 1;
	long long i = result(x, y / 2);
	k = i*i % c;
	if (y % 2)
		return k * x% c;
	return k;
}
int main()
{
	cin >> a >> b >> c;
	cout << result(a, b);
}

djm03178 5년 전 1

덧셈과 곱셈으로만 이루어진 식에서는 언제 어디서든 mod를 해도 됩니다.

쉬운 예시로, 10진법의 수로 덧셈과 곱셈으로만 이루어진 식에서 1의 자리를 구해야 하는 경우를 생각해 보면 나머지는 무시하고 항상 1의 자리만 보더라도 된다는 것을 알 수 있습니다. 마찬가지로 c진법의 수에서 덧셈과 곱셈으로만 이루어진 식이 있다면 c로 나눈 나머지, 즉 c진법에서 마지막 자리의 수만 추적하더라도 결과는 같습니다.

dranger97 5년 전 0

이 문제를 푸실 때는 13171번 문제를 참고하시기 바랍니다.

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

문제

문제

출처

ICPC

1629 곱셈 질문 하나

dolmul5000 5년 전 1

djm03178 5년 전 1

dranger97 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말