모듈러 연산의 분배법칙

예시문제

https://www.acmicpc.net/problem/1629

 

모듈러 연산의 분배법칙

모듈러 연산이 그대로 분배법칙이 성립한다는 것은 아니다.

'모듈러 연산은 결과값에 한번 더 모듈러를 취해주면 분배법칙이 성립한다'.

 

0. a ≡ b mod n과 b ≡ c mod n 은 a ≡ c mod n 을 의미 

1. [(a mod n)+(b mod n)] mod n = (a+b) mod n
2. [(a mod n)-(b mod n)] mod n = (a-b) mod n
3. [(a mod n)*(b mod n)] mod n = (a*b) mod n

 

1. (a + b) % n 은 (a % n) + (b % n) 을 다시 %n 한 것과 같다.
2. (a - b) % n 은 (a % n) - (b % n) 을 다시 %n 한 것과 같다. 
3. (a * b) % n 은 (a % n) * (b % n) 을 다시 %n 한 것과 같다. 

 

내 풀이

분할 정복 문제.

모듈러연산의 분배법칙과 분할 정복을 사용하자.

#include <iostream>
using namespace std;

int a, b, c;

long long Mult(long long n)
{
    if (n == 1)
        return a % c;

    long long result = Mult(n / 2);
    result = (result * result) % c;

    if (n % 2 == 1)
        result = (result * a) % c;
    
    return result;
}

int main(void)
{
    cin >> a >> b >> c;
    cout << Mult(b);
}