C++로 특정 범위에서 A 또는 B로 나누어 떨어지는 수의 개수 구하기

문제 소개

정수 네 개 L, R, A, B가 주어집니다. 목표는 범위 [L, R]에 속한 수 중에서 A 또는 B(혹은 둘 다)로 나누어 떨어지는 수의 개수를 구하는 것입니다.

가장 단순한 방법은 L부터 R까지 차례대로 순회하면서 각 수를 확인하는 것입니다. 어떤 수 i를 A로 나눈 나머지가 0이거나(i % A == 0), B로 나눈 나머지가 0이라면(i % B == 0) 카운트를 1씩 증가시키면 됩니다.

예제를 통해 자세히 살펴보겠습니다.

예제

입력 − L=10, R=15, A=4, B=3

출력 − 조건을 만족하는 수의 개수: 2

설명 −

12는 3과 4 모두로 나누어 떨어집니다.
15는 3으로만 나누어 떨어집니다.
총 개수 = 2

입력 − L=20, R=30, A=17, B=19

출력 − 조건을 만족하는 수의 개수: 0

설명 − 20부터 30 사이에는 17이나 19, 혹은 둘 다로 나누어 떨어지는 수가 하나도 없습니다.

알고리즘 접근 방법

변수 L, R, A, B를 입력받습니다.
countDivisors(int l, int r, int a, int b) 함수는 범위 [L, R]에서 A 또는 B로 나누어 떨어지는 수의 개수를 계산해 반환합니다.
카운트를 0으로 초기화합니다.
i를 L부터 R까지 1씩 증가시키며, i % a == 0 또는 i % b == 0이면 카운트를 증가시킵니다.
반복문이 끝나면 카운트에는 조건을 만족하는 수의 총개수가 저장되어 있습니다.
카운트를 결과값으로 반환합니다.

C++ 구현 예제

#include <bits/stdc++.h>
using namespace std;

int countDivisors(int l, int r, int a, int b){
    int count = 0;
    for (int i = l; i <= r; i++){
        if(i % a == 0 || i % b == 0){
            count++;
        }
    }
    return count;
}

int main(){
    int L = 5;
    int R = 15;
    int A = 2;
    int B = 5;
    cout << endl << "A 또는 B로 나누어 떨어지는 수의 개수 : " << countDivisors(L, R, A, B);
    return 0;
}

실행 결과

위 코드를 실행하면 다음과 같은 출력이 생성됩니다 −

A 또는 B로 나누어 떨어지는 수의 개수 : 7

범위 [5, 15]에서 2 또는 5의 배수는 5, 6, 8, 10, 12, 14, 15로 총 7개입니다.

시간 복잡도와 최적화 아이디어

위 방식의 시간 복잡도는 O(R − L + 1)입니다. 범위가 작다면 충분히 효율적이지만, L과 R 사이의 간격이 수억, 수조 단위로 크다면 전체를 순회하는 것은 비현실적입니다.

이럴 때는 포함-배제 원리(Inclusion-Exclusion Principle)를 활용하면 반복 없이 상수 시간에 답을 구할 수 있습니다.

구간 [L, R]에서 x의 배수 개수 = R / x − (L − 1) / x (정수 나눗셈)
A의 배수 개수와 B의 배수 개수를 더한 뒤, 최소공배수 lcm(A, B)의 배수 개수를 빼면 두 조건에 모두 해당하는 중복이 제거됩니다.

#include <bits/stdc++.h>
using namespace std;

long long countMultiples(long long l, long long r, long long x){
    return r / x - (l - 1) / x;
}

long long gcd(long long a, long long b){
    return b == 0 ? a : gcd(b, a % b);
}

int main(){
    long long L = 5, R = 15, A = 2, B = 5;
    long long l = A / gcd(A, B) * B; // 최소공배수
    long long result = countMultiples(L, R, A)
                     + countMultiples(L, R, B)
                     - countMultiples(L, R, l);
    cout << endl << "A 또는 B로 나누어 떨어지는 수의 개수 : " << result;
    return 0;
}

두 방법 모두 동일한 결과인 7을 출력하지만, 후자는 범위가 아무리 커도 거의 일정한 시간 안에 답을 구할 수 있다는 강점이 있습니다.

마무리

구간 내에서 특정 수의 배수를 세는 문제는 코딩 테스트에서 자주 등장하는 유형입니다. 범위가 작을 때는 단순 순회로 충분하고, 범위가 클 때는 포함-배제 원리를 떠올리면 효율적으로 해결할 수 있습니다.