728x90
반응형
이 문제는 시간 제한이 1초인 것에 유의해야하는 문제이다.
두 자연수의 최소 공배수까지 반복문을 돌며 나머지 값과 동일한 경우를 구하게 되면
40000 * 40000 이상의 연산은 1초를 넘게 되서 시간 초과가 난다.
참고로 최소 공배수까지 반복문을 도는 이유는,
최소 공배수를 기점으로 나머지가 0이 되기 때문에 x: y 또한 m: n이 될 것이므로,
그 이상의 수를 반복시킬 이유는 없어진다.
예를 들어 m:n = 10 : 12 일 경우, 최소 공배수는 60으로
x : y |
k번째 해 |
10:12 |
60 |
1 : 1 |
61 |
10: 12 |
120 |
1: 1 |
121 |
60을 주기로 계속 반복되는 것을 관찰 할 수 있다.
그렇다면 어떻게 시간 제한을 1초 내로 줄일 수 있을까?
반복문은 굳이 최소 공배수까지 돌 필요가 없다.
for(int i = 0; (x * i + m) <= a * b / gcd; i++)
이 정도의 반복문을 돌면 된다.
(참고로 a * b / gcd는 최소 공배수를 의미한다.)
k 번째 해에 해당하는 k mod n은 y인지 보면되기 때문이다.
for(int i = 0; (i*m+x) <= gcd * divideM * divideN; i++){
if((i*m+x) % n == y || ((i*m+x) % n == 0 && y == n) ){
cout << i*m + x << "\n";
isPossible = true;
break;
}
}
참고로 mod n = 0 일 경우 y는 n이라는 것을 유의해야한다.
따라서 코드는 이렇다.
//카잉 달력
#include <iostream>
using namespace std;
int uclid(int a, int b){
while(a % b != 0){
int n = a % b;
a = b;
b = n;
}
return b;
}
int main(void){
int test;
cin >> test;
while(test--){
bool isPossible = false;
int m,n,x,y;
cin >> m >> n >> x >> y;
int gcd = uclid(m, n);
int divideM = m / gcd;
int divideN = n / gcd;
for(int i = 0; (i*m+x) <= gcd * divideM * divideN; i++){
if((i*m+x) % n == y || ((i*m+x) % n == 0 && y == n) ){
cout << i*m + x << "\n";
isPossible = true;
break;
}
}
if(!isPossible) cout << -1 << "\n";
}
}
반응형
'algorithm' 카테고리의 다른 글
[algorithm] 백준 - 소인수분해 (0) | 2020.11.13 |
---|---|
[algorithm] 백준 - 부분 수열의 합 2 (0) | 2020.11.10 |
[algorithm] 백준 - 외판원 순회 2 (0) | 2020.11.06 |
[algorithm] 백준 - 숨바꼭질 4 (0) | 2020.11.05 |
[algorithm] 백준 - 숨바꼭질 6 (0) | 2020.11.04 |