[c++] 백준 1629 - 곱셈(분할 정복인데 비트마스크 활용?)

0. [c++] 백준  -

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

1. 풀이

비트마스크를 활용해서 2^32이내의 연속된 곱셈의 결과를 빠르게 구해보았다.

2. 소스코드

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52

#include<iostream>   using namespace std;   typedef unsigned long long ull;   ull A, B, C;   ull cache[50]; bool visited[50]; ull ret = 1;   void calc() {     ull copy_A = A;     ull copy_B = B;     ull power = 0;          while (copy_B > 1) {         //비트마스크의 방식을 활용해서 B에 활용되는 2진수를 찾자.         if (copy_B % 2)             visited[power] = true;         copy_B /= 2;           //cache[i]에 A를 2^i번 곱한 값을 넣어준다.         cache[power] = copy_A % C;         copy_A *= copy_A;         copy_A %= C;           //power을 한차례 증가시켜준다.         power++;     }     visited[power] = true;       //이진수로 변경한 수에 담겨있는 값을 구해야 하는 답과 곱해준다.     for (int i = 0; i <= power; i++) {         if (visited[i]) {             ret *= cache[i];             ret %= C;         }     } }   int main() {     ios_base::sync_with_stdio(0);     cin.tie(0);       cin >> A >> B >> C;     calc();     cout << ret;       return 0; } Colored by Color Scripter

cs

3. 참고

질문이나 지적 있으시면 댓글로 남겨주세요~

도움 되셨으면 하트 꾹!