//수치계산 목678 박정욱
//gcd,lcm,st 구하기
#include<stdio.h>
int get_gcd(int A,int B); //유클리드 알고리즘을 이용해 gcd을 리턴해주는 함수.
int get_lcm(int A,int B); //(A * B) / gcd 를 계산하여 lcm을 리턴해주는 함수.
void get_st(int A,int B); //gcd == s*A +t*B일때의 s와 t값을 리턴해주는 함수.
void main() //main 함수.
{ //선언
int A,B,tmp; //입력받는 값 A와 B. 임시저장변수 tmp.
int gcd,lcm; //gcd와 lcm값을 입력받을 변수.
//입력
printf("A와 B를 입력하시오.\n");
scanf("%d %d",&A,&B);
if(B >A) {tmp = A; A=B;B=tmp;} //함수호출간 오류를 최소화하기 위해 큰 수를 A로 둔다.
//함수 호출
gcd = get_gcd(A, B); //get_gcd함수 호출. 리턴값을 gcd에 대입한다.
printf("gcd(A, B)=%d\n\n",gcd);
lcm = get_lcm(A, B); //get_lcm함수 호출. 리턴값을 lcm에 대입한다.
printf("lcm(A, B)=%d\n\n",lcm);
get_st(A, B); //get_st 함수 호출.
}
int get_gcd(int A,int B) //gcd 구하는 함수.
{ //선언
int r[3]; //r[0]=q*r[1]+r[2]
//초기화
r[0]=A; r[1]=B; r[2]=A%B; //A = q * B + A%B
//계산
while(r[2] != 0) //나머지가 0이 아닌경우 수행.
{// printf("%d=%d*%d+%d\n",r[0],r[0]/r[1],r[1],r[2]); //<-과정 출력
r[0]=r[1]; //r[0]=r[1]*q+r[2] 제수->피제수
r[1]=r[2]; // ↙ ↙ 나머지->제수
r[2]=r[0]%r[1]; //r[0]=q*r[1]+ r
}
//리턴
return r[1]; //나머지 r[2]가 0일때의 gcd값 r[1]을 리턴한다.
}
int get_lcm(int A,int B) //lcm 구하는 함수
{ //리턴
return A*B/get_gcd(A, B); //A*B의 값을 gcd로 나누면 lcm이다.
}
void get_st(int A,int B) //s와 t를 구하는 함수.
{ //선언
int r[3] ,i=0; //r[0]=q*r[1]+r[2] if(r[2]==0){gcd=r[1]=(s[2]*A)+(t[2]*B)}
int s[3]={0},t[3]={0},q[3]={0}; //배열 s,t,q의 선언 및 초기화.
//초기화
r[0]=A; r[1]=B; r[2]=A%B; //A = q * B + A%B
//계산
while(r[1] != s[2]*A+t[2]*B) //r[1](gcd)=(s*A+t*B) 인 s와 t를 찾을때 까지 수행(수행 후 i증가).
{ if(i == 0)
{ s[2]= 1; t[2]= 0; } //S0= 1, T0= 0
else if(i == 1)
{ s[2]= 0; t[2]= 1; } //S1= 0, T1= 1
else
{ s[2] = s[0]-q[0]*s[1];
t[2] = t[0]-q[0]*t[1];} //Sn=S(n-2)-Q(n-2)*S(n-1) Tn=T(n-2)-Q(n-2)*T(n-1)
q[2] = r[0]/r[1]; //몫의 초기화.
//r[0]=q*r[1]+r[2]
if(r[2] !=0)
{ r[0]=r[1]; r[1]=r[2];
r[2]=r[0]%r[1]; } //gcd 값을 구할때까지 수행; 나머지가 0일떄까지 수행.
s[0]=s[1];s[1]=s[2]; //항들의 이동.
t[0]=t[1];t[1]=t[2]; //배열 s,t,q는 요소가 3개뿐이므로, 재사용을 위해
q[0]=q[1];q[1]=q[2]; //2->1 1->0 으로 요소들을 이동시킨다.
i++; //i증가
}
//출력
printf("gcd=(s*A)+(t*B)\n"); //gcd=(s*A)+(t*B)
printf("gcd=%d=(%d*%d)+(%d*%d)\n\n",r[1],s[2],A,t[2],B);
}