백준 15576 - 큰 수 곱셈 (2)

www.acmicpc.net/problem/15576

15576번: 큰 수 곱셈 (2)

 

#include <iostream>
#include <complex>
#include <vector>
#include <cstring>
#include <string>
#include <algorithm>
 
// Koosaga 팀노트 FFT 코드
using namespace std;
typedef complex<double> base;
typedef long long ll;
const double PI = acos(-1);
 
void fft(vector<base>& a, bool inv = false) {
    int n = a.size(), j = 0;
    // 분할 정복 기법, 이때 n은 무조건 2^n 승임
    vector<base> roots(n / 2);
    for (int i = 1; i < n; i++) {
        int bit = (n >> 1);
        while (j >= bit) {
            j -= bit;
            bit >>= 1;
        }
        j += bit;
        if (i < j) swap(a[i], a[j]);
    }
    double ang = 2 * acos(-1) / n * (inv ? -1 : 1);
    for (int i = 0; i < n / 2; i++) {
        roots[i] = base(cos(ang * i), sin(ang * i));
    }
    for (int i = 2; i <= n; i <<= 1) {
        int step = n / i;
        for (int j = 0; j < n; j += i) {
            for (int k = 0; k < i / 2; k++) {
                base u = a[j + k], v = a[j + k + i / 2] * roots[step * k];
                a[j + k] = u + v;
                a[j + k + i / 2] = u - v;
            }
        }
    }
    if (inv) for (int i = 0; i < n; i++) a[i] /= n;
}
 
vector<ll> multiply(vector<ll>& v, vector<ll>& w) {
    vector<base> fv(v.begin(), v.end()), fw(w.begin(), w.end());
    // n이 무조건 2^n 이여야 하기 때문에 변환!
    int n = 2; while (n < v.size() + w.size()) n <<= 1;
    fv.resize(n); fw.resize(n);
    fft(fv, 0); fft(fw, 0);
    for (int i = 0; i < n; i++) fv[i] *= fw[i];
    fft(fv, 1);
    vector<ll> ret(n);
    for (int i = 0; i < n; i++) ret[i] = (ll)round(fv[i].real());
    return ret;
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    string str1, str2;
    cin >> str1 >> str2;
    // 둘 중 하나라도 0이면 예외처리
    if (str1 == "0" || str2 == "0") {
        cout << 0 << "\n";
        return 0;
    }
    vector<ll> a(str1.size()), b(str2.size());
    for (int i = 0; i < str1.size(); i++)a[str1.size() - i - 1] = str1[i] - '0';
    for (int i = 0; i < str2.size(); i++)b[str2.size() - i - 1] = str2[i] - '0';
    vector<ll> ret = multiply(a, b);
 
    // 배열의 마지막부터 채우면서 ret에 들어있는 값들을 더해줌
    // 이 때 원래 라면 매 진행마다 10을 곱해줘야 하는데 그러면 오버플러우 날 것 같아서
    // 10을 곱해주는 대신 자리수를 하나 올려줌으로써 해결(ten 변수가 자리수 한자리씩 올려주는 변수)
    /*ex)123 * 456 이라면
          18       <- ret[0]
         27        <- ret[1]
        28         <- ret[2]
       13          <- ret[3]
       4           <- ret[4]
    =  56088 
    */
 
    for (int i = 0; i < str1.size() + str2.size() - 1; i++) {
        ret[i + 1] += ret[i] / 10;
        ret[i] = ret[i] % 10;
    }
    int cnt = ret.size() - 1;
    while (ret[cnt] == 0) {
        cnt--;
        if (cnt == 0) break;
    }
    for (int i = cnt; i >= 0; i--) cout << ret[i];
    cout << "\n";
}