큰 수의 나눗셈_모듈러 연산 & 분할정복

(A + B) % C = ((A % C) + (B % C)) % C

(A - B) % C = ((A % C) - (B % C)) % C

(A * B) % C = ((A % C) * (B % C))) % C

모듈러 연산 (더 알고싶으면 유클리드 호제법 검색하기.)

 

이를 이용하여

(A1 * A2 *  ... * An) % C

(A1 * A2 * .. * An) 을 다 계산하게 되면 수가 매우 커지게 되며 시간복잡도 또한 O(n) 이 되게 된다.

따라서 우리는 위와 같이 모듈러 연산을 사용하면 시간복잡도 및 연산의 결과가 자료형의 크기를 벗어나며 오류가 나는 상황을 막을 수 있다.

((A1 * A2 * A3 * ... * An-1) % C * (An % C)) % C

너무 안예쁜데..

훔..

 

위와 같은 모듈러 연산을 분할을 통해 계산을 하면 된다.

완전이진트리, 퀵소트와 같이 절반씩 잘라가면서 수행하는 연산이 제일 속도가 빠르므로

나누기 2를 하며 홀수가 나오면 a를 한번 더 곱해준 상황에서 연산을 하게 로직을 구현했다.

 

또한 result에 내용을 넣어서 처리하면 어짜피 마지막 b=1 일 때 걸리기 때문에 같이 넣어서 구현했다.

 

백준 1629번 소스코드이다.

#include <iostream> #include <stdio.h> #include <vector> #include <string> #include <algorithm> using namespace std; long long result = 1; long long divide(long long a, long long b, long long c) {          a %= c;     // 2,147,483,647를 한번이라도 곱하는 순간 범위 초과하지않아..?     // 모듈러 연산에 의해 나머지를 구하기 위해서 나머지를 사용해도 결과는 같음.          while (b>0) {                  // b가 1일 때 즉 제일 밑단에 있는 친구가 등장 할 때 result에 곱하고 나누면서 결과 확인         if(b%2==1) {             // b가 홀수일 경우에는 /2 한거에 *를 한번 더 해줘야 하기 때문.             result *= a;             result %= c;         }                  a = ((a%c) * (a%c)) %c;                  b /=2;     }          return result;      } int main() {          ios_base::sync_with_stdio(false);     cin.tie(NULL);              long long A,B,C;     cin >> A >> B >> C;                    cout << divide(A, B, C);;          return 0; }