문제 개요
두 정수 A와 B가 주어졌을 때, A % X = B를 만족하는 X 값이 총 몇 가지인지 구하는 것이 이 문제의 목표입니다. A와 B의 크기 관계에 따라 답이 완전히 달라지므로, 먼저 세 가지 경우를 살펴보겠습니다.
- A == B인 경우: X가 A보다 크기만 하면 A % X = A = B가 항상 성립하므로 가능한 X는 무한히 많습니다. 이때는 -1을 반환합니다.
- A < B인 경우: 나머지는 항상 나누는 수보다 작고 A 자신을 넘을 수도 없으므로, A % X = B를 만족하는 X는 존재하지 않습니다. 이때는 0을 반환합니다.
- A > B인 경우: (A − B)의 약수 중 B보다 큰 값의 개수를 결과로 반환합니다.
예시
입력
A=5, B=2
출력
Count of all possible values of X such that A % X = B are: 1
설명
5 % 3 = 2이므로 X = 3이 조건을 만족합니다. 실제로 (A − B) = 3의 약수 중 B(=2)보다 큰 값은 3 하나뿐입니다.
입력
A=10, B=10
출력
Count of all possible values of X such that A % X = B are: -1
설명
A == B이므로 무한히 많은 해가 존재하며, -1을 반환합니다.
접근 방법
이 문제의 핵심은 나머지 연산의 기본 성질입니다. A % X = B가 성립하면 A = q × X + B (q는 1 이상의 정수) 형태로 표현할 수 있고, 양변에서 B를 빼면 A − B = q × X가 됩니다. 즉, X는 반드시 (A − B)의 약수여야 하며, '나머지는 나누는 수보다 작다'는 조건에 의해 X > B도 동시에 만족해야 합니다.
따라서 (A − B)의 모든 후보를 일일이 확인하는 대신, i = 1부터 i × i ≤ (A − B)까지만 순회하며 약수를 짝지어 찾으면 시간 복잡도 O(√(A − B))로 효율적으로 문제를 해결할 수 있습니다.
- 정수 A와 B를 입력받습니다.
- A < B이면 0을 출력합니다.
- A == B이면 -1을 출력합니다.
- A > B이면 possible_values(int A, int B) 함수가 조건을 만족하는 X의 개수를 계산하여 반환합니다.
- count는 0으로, X는 A − B로 초기화합니다.
- i = 1부터 i × i ≤ (A − B)까지 반복하며 X의 약수를 찾습니다.
- i가 X를 나누어떨어지면 temp = i로 설정하고, i × i ≠ X이면 temp_2 = X / i로 설정하여 짝이 되는 약수도 함께 확인합니다.
- temp > B 또는 temp_2 > B이면 count를 증가시킵니다.
- 반복문이 끝나면 count를 결과로 반환합니다.
C++ 예제 코드
#include <bits/stdc++.h>
using namespace std;
int possible_values(int A, int B){
int count = 0;
int X = A - B;
for (int i = 1; i * i <= A - B; i++){
if(X % i == 0){
int temp = i;
int temp_2 = B - 1;
if(i * i != X){
temp_2 = X / i;
}
if(temp > B){
count++;
}
if(temp_2 > B){
count++;
}
}
}
return count;
}
int main(){
int A = 15, B = 5;
if(A < B){
cout<<"Count of all possible values of X such that A % X = B are: "<<0;
}
else if(A == B){
cout<<"Count of all possible values of X such that A % X = B are: "<<-1;
}
else{
cout<<"Count of all possible values of X such that A % X = B are: "<<possible_values(A, B);
}
return 0;
}
실행 결과
위 코드를 실행하면 다음과 같은 결과가 출력됩니다.
Count of all possible values of X such that A % X = B are: 1
A = 15, B = 5인 경우 (A − B) = 10이며, 10의 약수는 1, 2, 5, 10입니다. 이중 B(=5)보다 큰 약수는 10뿐이므로 결과는 1이 됩니다. 실제로 15 % 10 = 5가 성립하는 것을 확인할 수 있습니다.