c언어 - 확장 유클리드 알고리즘
확장 유클리드 알고리즘이란? 정수 m, n의 최대 공약를 gcd(m, n)으로 나타낼 때 1. 확장된 유클리드 호제법을 이용하여, am + bn = gcd(m,n)의 해가 되는 정수 a, b 짝을 찾아낼 수 있다. 2. 특히, m, n이 서로소(gcd(m,n) = 1)인 경우 유용한데, 그럼 위의 식은 am + bn = 1이 되고, 여기서 a는 모듈러 연산의 곱의 역원(modular multiplicative inverse)이 되기 때문이다. 등식 : s*m + t*n = gcd(m, n) r = r1-q*r2 --> r1 = q*r2 + r //초기 r1, r2는 (m, n)이고 q는 몫 r은 나머지 s = s1-q*s2 //초기 s1, s2는 1, 0이다. t = t1-q*t2 //초기 t1, t2는..
2012. 5. 26.
c언어 - 유클리드 알고리즘
유클리드 알고리즘이란? - 두 양의 정수들에 대한 최대 공약수를 찾아내기 위한 알고리듬 등식 : gcd(a,b) = gcd(b,a mod b) ex) gcd(44, 12)=gcd(12, 8) = gcd(8,4) = gcd(4,0) = 4 44와 12의 최대 공약수 -> 4 c언어 소스 #include #include int Euclid(int num1, int num2); int main() { int num1, num2, gcd; printf("두 정수를 입력하세요 : "); scanf("%d %d", &num1, &num2); if(num1 > num2) gcd = Euclid(abs(num1), abs(num2)); //절댓값으로 넣음 else gcd = Euclid(abs(num2), abs(nu..
2012. 5. 26.
