[C++] 큰 수 연산

정의

long long 범위를 넘는 정수의 덧셈, 뺄셈, 나눗셈, 모듈러 연산을 계산한다

• 큰 수를 문자열로 입력 받아야 한다
• 곱셈은 고속 푸리에 변환(FFT)으로 해야 한다

 

큰 수의 덧셈 

큰 수 a와 b를 더하기 (추천 문제: 백준 10757번 큰 수 A+B)

string bigNum_add(string a, string b) {
	long long al = a.length(), bl = b.length();
    long long c = 0;
    string ans;

	for(long long i = 0; i < al || i < bl; i++) {
        if(i < al)
            c += a[al-i-1] - '0';
        if(i < bl)
            c += b[bl-i-1] - '0';
            
        ans += (c%10) + '0';
        c /= 10;
    }
     
    // 더하고 남은 값이 존재한 경우 붙여줌
    if(c != 0) ans += c + '0';
    
    // 문자열에 반대로 저장되므로 뒤집기
    reverse(ans.begin(), ans.end());
    
    return ans;
}

 

큰 수의 뺄셈

큰 수 a에서 b를 빼기

// 큰 수에서 작은 수를 빼기 위한 swap
bool check(string& a, string& b) {
    // 길이가 길면 무조건 큼
    if(a.length() > b.length())
        return false;
    else if(a.length() < b.length()) {
        swap(a,b);
        return true;
    }
 
    // 길이가 같으면 한자리씩 비교
    for(int i=0; i<a.length(); i++) {
        if(a[i] > b[i])
            return false;
        else if(a[i] < b[i]) {
            swap(a,b);
            return true;
        }
    }
    return false;
}

string bigNum_sub(string a, string b) {
    bool cr = false, flag = check(a, b);
    long long al = a.length(), bl = b.length();
    long long c = 0;
    string ans;
    
	for(long long i = 0; i < al || i < bl; i++) {
        if(i < al) {
            c += a[al-i-1] - '0';
            
            // 캐리 처리
            if(cr) { 
            	c--; 
                cr = false;
        	}
        }
        if(i < bl)
            c -= b[bl-i-1] - '0';
        
        // 뺀 값이 음수일 시 보수, 캐리 체크
        if(c < 0) {
            c = 10-abs(c);
            cr = true;
        }
        
        ans += c + '0';
        c = 0;
    }
    
    // 최종 값이 0이 아닌 경우, 맨 앞이 0이면 제거
    if(ans.back() == '0' && ans.length() > 1) ans.pop_back();
    
    // check()에서 swap된 경우 음수
    if(flag) ans += '-';
    
	// 문자열에 반대로 저장되므로 뒤집기
    reverse(ans.begin(), ans.end());
    
    return ans;
}

 

큰 수의 나눗셈

큰 수 a를 b로 나눈 몫 구하기 (제수는 long long 범위 이내)

string bigNum_div(string a, long long b) {
    long long c = 0;
    string ans;
    
	for(long long i = 0; i < a.length(); i++) {
        c = (c * 10) + (a[i] - '0');
        ans += (c / b) + '0';
        c %= b;
    }
    
    return ans;
}

 

큰 수의 모듈러

큰 수 a를 b로 나눈 나머지 구하기 (제수는 long long 범위 이내)

long long bigNum_mod(string a, long long b) {
    long long c = 0;

	for(long long i = 0; i < a.length(); i++) {
        c = (c * 10) + (a[i] - '0');
        c %= b;
    }
    
    return c;
}