문제
limit 미만의 양의 정수들을 고려하세요. 값이 0이 아닌 인수 중 적어도 하나로 나누어떨어지면 해당 값을 포함합니다. 여러 인수로 나누어떨어지더라도 각 값은 한 번만 포함하여 계산합니다. 0인 인수는 무시합니다. 인수가 [3, 5]인 경우 익숙한 3 또는 5의 배수 문제와 같습니다.
sum_of_multiples(limit, factors)를 구현하세요.
입력
limit: 배타적인 상한값입니다.
factors: 배수를 판별할 인수들의 리스트입니다.
출력
조건을 만족하는 서로 다른 양의 정수들의 합을 반환하세요.
제약 조건
0 ≤ limit ≤ 100,000. 인수는 0개에서 20개까지 주어질 수 있으며, 각 인수는 0 이상 100,000 이하입니다. 중복된 인수가 있을 수 있습니다.
예시
예시 1
입력:
limit = 12
factors = [3, 5]
예상 출력:
expected = 33입력:
long long limit = 12;
std::vector<long long> factors = {3, 5};
예상 출력:
long long expected = 33;입력:
long limit = 12;
long[] factors = new long[] {3, 5};
예상 출력:
long expected = 33;설명
포함되는 값은 3, 5, 6, 9, 10입니다. 이들의 합은 33입니다.
예시 2
입력:
limit = 10
factors = [2, 4]
예상 출력:
expected = 20입력:
long long limit = 10;
std::vector<long long> factors = {2, 4};
예상 출력:
long long expected = 20;입력:
long limit = 10;
long[] factors = new long[] {2, 4};
예상 출력:
long expected = 20;설명
2, 4, 6, 8을 포함합니다. 4와 8은 두 인수 모두에 해당하지만 한 번만 계산됩니다.
접근 방법
먼저 스스로 풀어 본 뒤 힌트를 하나씩 열어 보세요.
힌트 1
적어도 하나의 유효한 약수로 나누어떨어지는 값만 한 번만 더한다.
힌트 2
포함-배제를 써서 겹치는 배수들을 중복 없이 합친다.
힌트 3
계산 전에 0인 약수와 중복 약수는 제거한다.
예상 복잡도
시간 O(2^m), 추가 공간 O(1)
참고 자료
이 문제는 CodeUtility에 맞게 수정되었습니다. 위의 설명과 제한 조건을 따르세요.