C++로 큰 수 N을 4로 나눈 나머지(N % 4) 구하기

이 문제에서는 매우 큰 정수를 나타내는 문자열 num이 주어지며, 우리의 과제는 이 큰 수 N에 대해 4로 나눈 나머지(N % 4)를 구하는 것입니다.

문제 설명

주어진 숫자를 4로 나누었을 때의 나머지를 계산하는 것이 목표입니다.

예제로 문제 이해하기

입력

num = 453425245

출력

1

해결 접근 방법

이 문제를 해결하는 간단한 방법은 다음과 같은 수학적 성질을 활용하는 것입니다. 어떤 수를 4로 나눈 나머지는 그 수의 마지막 두 자리 숫자만으로 구할 수 있습니다.

그 이유는 100이 4로 나누어떨어지기 때문입니다. 즉, 100으로 나눈 몫에 해당하는 앞자리 부분은 항상 4의 배수이므로 나머지 계산에 영향을 주지 않습니다. 따라서 아무리 큰 숫자라도 마지막 두 자리만 4로 나누면 전체 숫자의 나머지를 쉽게 얻을 수 있습니다.

숫자가 한 자리뿐인 경우에는 그 숫자 하나만으로 나머지를 계산하면 됩니다.

구현 예제

#include <bits/stdc++.h>
using namespace std;
int calc4Mod(string num, int len) {
    int rem;
    if (len == 1)
        rem = num[0] - '0';
    else
        rem = (num[len - 2] - '0') * 10 + num[len - 1] - '0';
        return (rem % 4);
}
int main() {
    string num = "84525765476513";
    int len = num.length();
    cout<<"The remainder of the number with 4 is "<<calc4Mod(num, len);
    return 0;
}

출력 결과

The remainder of the number with 4 is 1

코드 설명

calc4Mod 함수는 문자열 형태의 숫자와 그 길이를 매개변수로 받습니다. 숫자가 한 자리인 경우 해당 문자를 정수로 변환하고, 두 자리 이상인 경우 뒤에서 두 번째 문자에 10을 곱한 후 마지막 문자를 더하여 마지막 두 자리 값을 만듭니다. 최종적으로 이 값을 4로 나눈 나머지를 반환합니다.

이 방법의 시간 복잡도는 O(1)로, 숫자가 아무리 커도 상수 시간 안에 결과를 구할 수 있다는 것이 가장 큰 장점입니다. 실제로 자릿수가 수천 자리에 달하는 초대형 숫자도 문자열로 처리하면 손쉽게 나머지를 계산할 수 있습니다.