이 문제는 기본적인 문젠데 너무 삽질을 오래했다.
x를 먼저 찾고, 거기에서 M씩 더해가며 y가 일치하는 연도를 찾으면 빨리 찾을 수 있다!
UB는 M과 N의 최소공배수다. ^_^
#include <stdio.h>
#include <stdlib.h>
int lcm(int a, int b) {
int r, prod = a*b;
if (a < b) {
int tmp = a;
a = b;
b = tmp;
}
while(b) {
r = a % b;
a = b;
b = r;
}
return prod / a;
}
int main() {
int t;
scanf("%d", &t);
while(t--) {
int M, N, x, y;
scanf("%d%d%d%d", &M, &N, &x, &y);
int limit = lcm(M, N);
int tmpy = x;
while(tmpy <= limit) {
if (y%N == tmpy%N)
break;
tmpy += M;
}
if(tmpy > limit)
printf("-1\n");
else printf("%d\n", tmpy);
}
return 0;
}
갑자기 c로 푼 이유는 알고리즘 강의 끝나고 바로 풀었기 때문이당 별 이유도 없고 또 쓸 일도 없을 거같다
이 문제가 자료 구조를 쓸 일이 없어서 c로 풀 수 있었던 것 같다.
불쌍한 c 언어 가끔씩 켜주세요,,,