void normalize(vector<int>& num){
num.push_back(0);
//자릿수 올림을 처리한다
for(int i = 0 ; i < num.size() ; i++){
if(num[i] < 0){//자릿수가 음수일 경우도 처리 가능. 이것은 카라츠바를 위해 있다
int borrow = (abs(num[i]) + 9) / 10;
num[i+1] -= borrow * 10;
num[i] += borrow * 10;
}
else{
num[i+1] += num[i] / 10;
num[i] %= 10;
}
}
while(num.size() > 1 && num.back() == 0) num.pop_back();
}

//두 긴 정수의 곱을 반환한다(O(n^lg3) 알고리즘)
vector<int> karatsuba(const vector<int>& a, const vector<int>& b){
int an = a.size(), bn = b.size();
//a가 b보다 짧을 경우 둘을 바꾼다
if(an < bn) return karatsuba(b, a);
//기저 사례 : a나 b가 비어있는 경우
if(an == 0 || bn == 0) return vector<int>();
//기저 사례 : a가 비교적 짧은 경우 O(n^2) 로 계산
if(an <= 50) return multyply(a, b);
int half = an/2;
//a와 b를 밑에서 half 자리와 나머지로 분리한다.
vector<int> a0(a.begin(), a.begin() + half);
vector<int> a1(a.begin() + half, a.end());
vector<int> b0(b.begin(), b.begin() + min<int>(b.size(),half));
vector<int> b1(b.begin() + min<int>(b.size(),half), b.end());
//z2 = a1 * b1
vector<int> z2 = karatsuba(a1, b1);
//z0 = a0 * b0
vector<int> z0 = karatsuba(a0, b0);
//a0 = a0 + a1; b0 = b0 + b1
addTo(a0, a1, 0); addTo(b0, b1, 0);
//z1 = (a0*b0) - z0 - z2
vector<int> z1 = karatsuba(a0, b0);
subFrom(z1,z0);
subFrom(z1,z2);
//ret = z0 + z1 * 10^half + z2 * 10^(half*2)
vector<int> ret;
addTo(ret, z0, 0);
addTo(ret, z1, half);
addTo(ret, z2, half + half);
return ret;
}





normalize 에서 음수처리가 왜 필요한건지 모르겠어영