#include<stdio.h>
#include<conio.h>
void main()
{
int a,b,r1,r2,q,r,s1,s2,s,t1,t2,t,gcd,ans,c;
clrscr();
printf("0:EUCLIDIAN\n");
printf("1:EXTENDED EUCLIDIAN\n");
printf("Plese enter your choice\n");
scanf("%d",&c);
if(c==1)
{
printf("Enter the numbers to find GCD\n");
printf("Enter r1 and r2:\n");
scanf("%d%d",&a,&b);
r1=a;
r2=b;
s1=1;
s2=0;
t1=0;
t2=1;
while(r2>0)
{
q=r1/r2;
r=r1-(r2*q);
r1=r2;
r2=r;
s=s1-(q*s2);
s1=s2;
s2=s;
t=t1-(q*t2);
t1=t2;
t2=t;
}
gcd=r1;
s=s1;t=t1;
ans=(s*a)+(t*b);
printf("\nGCD For %d and %d GCD(%d,%d) is : %d",a,b,a,b,gcd);
printf("\nGCD For %d and %d GCD(%d,%d) is (%d*%d)+(%d*%d)=%d",a,b,a,b,s,a,t,b,ans);
}
else
{
printf("Enter the numbers to find GCD\n");
printf("Enter r1 and r2 :\n");
scanf("\t%d\t%d",&r1,&r2);
a=r1;
b=r2;
while(b>0)
{
q=a/b;
r=a-(b*q);
a=b;
b=r;
}
gcd=a;
printf("\nGCD For %d and %d GCD(%d,%d) is : %d",r1,r2,r1,r2,gcd);
}
getch();
}
output:
