문제 설명
두 개의 정수 p와 q가 주어지면 q % x =0 및 x % p =0이 되도록 가능한 최소 숫자 x를 찾는 작업입니다. 조건이 어떤 숫자에 대해서도 참이 아닌 경우 -1을 인쇄합니다.
예시
If p = 3 and q = 66 then answer is 3 as: 66 % 3 = 0 3 % 3 = 0
알고리즘
- 만약 x가 주어진 조건을 만족한다면, x는 p의 배수이고 q는 x의 배수이기 때문에 q는 p로 나누어질 것이 분명합니다. 즉, q % p =0입니다.
- 따라서 x의 가능한 최소값은 p와 q의 GCD가 될 것이며 q가 p로 나누어지지 않을 때 주어진 조건을 만족하는 숫자는 없을 것입니다
예시
#include <bits/stdc++.h>
using namespace std;
int getMinValue(int p, int q) {
if (q % p == 0) {
return __gcd(p, q);
}
return -1;
}
int main() {
int p = 3;
int q = 66;
cout << "Minimum value = " << getMinValue(p, q) << endl;
return 0;
} 위의 프로그램을 컴파일하고 실행할 때. 다음 출력을 생성합니다 -
출력
Minimum value = 3