모듈러 연산의 성질과, 아주 큰 두 수의 최대공약수

(이 글을 읽고 1234567891011121314151617181920212223242526272829와 1221의 최대공약수를 계산해보세요) 모듈러 연산 모듈러 연산은 a를 b로 나누었을 때의 나머지 r을 구하는 연산으로 나머지 연산(mod)이라고 한다. 모듈러 연산의 성질은 다음과 같다. 이 성질 중에서 4번을 이용해서 밑의 아주 큰 두 수의 최대공약수 문제를 풀어보자. c 아주 큰 수의 나머지 연산 저번 글에서 큰 두 수의 최대공약수를 구하기 위해서 유클리드 호제법을 사용한다고 했다. 그런데 이번 글도 아주 큰 두 수의 최대공약수를 다룬다. 하지만 저번 글 과는 다르게 아주아주아주 큰 수이다. c++에서 종종 큰 수를 다룰 때 사용하는 자료형인 long long도 범위가 제한되어있다. 그렇기 때문에 long long이 담을 수 없는 수의 범위에 있는 수를 다루기 위해서 char 문자열을 사용할 것이다. but! char 문자열로는 자리올림이 있는 정수 계산을 구현하기 힘들다...

원문링크 : 모듈러 연산의 성질과, 아주 큰 두 수의 최대공약수