백준 1929번 곱셈(C++)

문제문제는 간단해 보이지만 쉽게 풀리지 않는다.필수적으로 알아야 하는게 있는데지수법칙 : a^(n+m) = a^n * a^m모듈러 성질 : (a*b)%c = (a%c * b%c)%c이 두가지를 알아야만 한다.지수법칙은 아마 왠만하면 알 것 같은데 모듈러 성질은 곱해서 나누던 나눠서 곱하든 값은 같다는 것이다.증명은 수학자들이 해뒀으니 위키백과를 보자.그냥 구현 하면 시간초과 납니다.(왜 저 정답률이겠어요..)정답 코드#include #include using namespace std; typedef long long ll; int A,B,C; ll p(ll x) { if (x == 1) return (A%C); ll k = p(x/2)%C; if (x%2 == 0) return (k * k % C); e..

원문링크 : 백준 1929번 곱셈(C++)