* 모듈러 연산(a * b) % n = ((a % n) * (b % n)) % n
문제에서 제시한 예시를 풀어서 설명하자면
10^11 % 12 = (10 * 10^5 * 10^5) % 12 = ( (10 % 12) * (10^5 % 12) * (10^5 % 12 ) ) % 12
= ( (10 % 12) * ((10 * 10^2 * 10^2) % 12) * ((10 * 10^2 * 10^2) % 12)) ) % 12
= ( (10 % 12) * ( (10%12) * (10^2 % 12) * (10^2 % 12) % 12 ) * ( (10%12 ) * (10^2 % 12) * (10^2 % 12) % 12 ) ) % 12
= ( (10 % 12) * ( (10%12) * ((10*10) % 12) * ((10*10) % 12) % 12) * ( (10%12) * (10^2 % 12) * (10^2 % 12) % 12) ) % 12
= ... * ( (10%12) * ( ((10%12) * (10%12))%12 ) * ( ((10%12) * (10%12)) % 12) * ...
이렇게 풀 수 있다.
C++)
#include <iostream>
using namespace std;
int calc(long long a, long long b, long long c) {
if (b == 1)
return a % c;
long long temp = calc(a, b / 2, c);
temp = temp * temp % c;
if (b % 2 == 0)
return temp;
return temp * a % c;
}
int main(void) {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int a, b, c;
cin >> a >> b >> c;
cout << calc(a, b, c);
return 0;
}
Python)
import sys
a, b, c = map(int, sys.stdin.readline().rstrip().split())
def calc(a, b, c):
if b == 1:
return a%c
temp = calc(a, b//2, c)
temp = temp * temp % c
if b%2 == 0:
return temp
return temp * a % c
print(calc(a,b,c))'백준 1 > 수학' 카테고리의 다른 글
| [백준 2903] 중앙 이동 알고리즘 (0) | 2023.09.07 |
|---|---|
| [백준 2417] 정수 제곱근 (0) | 2020.12.07 |
| [백준 1427] 소트인사이드 (0) | 2020.12.06 |
| [백준 1085] 직사각형에서 탈출 (0) | 2020.12.06 |
| [백준 2163] 초콜릿 자르기 (0) | 2020.12.06 |