일단 이 이중 반복문을 통하여 모든 m*n케이스를 찾아보려고 할 경우 제 시간안에 찾아볼 수 없다. 그렇기 때문에 특정 조건일 때만 돌아가도록 만들어줘야 한다.
이 문제는 결국 x+M*a=y+N*b 라는 a와 b에 관한 부정방정식을 푸는 것인데 결국 이는 답이 되는 수를 t라고 한다면 t%M==x t%N==y가 되도록 만들어줘야한다. 그렇기 때문에 while문에 들어가는 초기 변수가 j=x_target이 된 것이고 while문을 한번 돌때마다 x만큼 증가시켜주면서 만족하는 수가 있는지 확인해줘야한다.
한가지 유의해야할 점은 x==x_target && y==y_target일 때인데 사실 이 경우 x%x_target이 x가 아니라 0이므로 이때를 주의하여 코드를 작성해야한다. 또한 이 경우에는 gcd 유클리드 알고리즘을 이용하여 최소공배수를 구하고 답을 구했다.
아래는 소스코드이다!
#include <stdio.h>
#include <math.h>
int gcd(int x,int y)
{
if(y==0)
return x;
else
return gcd(y,x%y);
}
int main(void)
{
int n,x,y,x_target,y_target;
scanf("%d",&n);
for(int i=0;i<n;i++)
{
scanf("%d %d %d %d",&x,&y,&x_target,&y_target);
if(x==x_target)
x_target=0;
if(y==y_target)
y_target=0;
int result=-1;
int j=x_target;
while(j<=x*y)
{
if(j%y==y_target)
{
result=j;
if(x_target==0 && y_target==0)
{
//printf("enter!\n");
if(y>x)
{
int tmp=y;
y=x;
x=tmp;
}
int tmp=gcd(x,y);
//printf("gcd: %d\n",tmp);
result=x*y/gcd(x,y);
}
break;
}
j+=x;
}
printf("%d\n",result);
}
}
다른 풀이 방식으로는 처음에 M과 N의 최소공배수를 구하여 최소공배수를 넘어가지 않는 부분에서만 확인하는 것이다. (이렇게 하면 코드가 조금 더 짧고 break를 잘못쓸 수 있는 경우를 배제한다). 그 후
while(x <= limit) {
if (y%N == x%N)
break;
x += M;
}를 이용하여 x를 N으로 나눈 나머지가 y를 N으로 나눈 나머지와 같을 때 결국 N이 부정방정식을 성립하게 된다. 이렇게 풀이할 경우 x==x_target && y==y_t일때 예외처리를 안해줘도 된다는 장점이 있다.
또 x가 n으로 나누어 떨어질때를 방지하기 위할때 쓰는 방법이 있는데
x%n <=> (x-1)%n+1
i) x<n -> x%n는 x, (x-1)%n은 x-1이라서 +1해주면 x
ii) x=a*n -> x%n는 a*n%n이라서 0, (x-1)%n은 (a*n-1)%n은 ((a-1)*n+n-1)%n으로 n-1이라서 +1해주면 n
iii) x>n -> x%n은 (a*n+b)%n이라서 b, (x-1)%n은 (a*n+b-1)%n은 b-1이라서 +1해주면 b
따라서, % 연산에 대해 a%b == (a+c)%b-c 가 성립한다는 것을 알 수 있다.
그렇기 때문에 이 문제에서도
(j-1)%y+1==y_target
를 이용하면 더 간단히 풀 수 있다. 위에서 말한 두가지 방법을 합해 소스코드를 고쳐보면 아래와 같이 된다!
#include <stdio.h>
#include <math.h>
int gcd(int x,int y)
{
if(y==0)
return x;
return gcd(y,x%y);
}
int main(void)
{
int n,x,y,x_target,y_target;
scanf("%d",&n);
for(int i=0;i<n;i++)
{
scanf("%d %d %d %d",&x,&y,&x_target,&y_target);
int result=-1;
int max=x*y/gcd(x,y);
int j=x_target;
while(j<=max)
{
if((j-1)%y+1==y_target) // % 연산에 대해 a%b == (a+c)%b-c 가 성립한다 (c는 상수)
{
result=j;
}
j+=x;
}
printf("%d\n",result);
}
}
카잉 달력에 관한 반례와 FAQ이며 여기서 나온 테스트케이스를 가지고 코드를 확인하면 된다.