유클리드 호제법

www.acmicpc.net/problem/11778 11778번: 피보나치 수와 최대공약수 첫째 줄에 n과 m이 주어진다. n과 m은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 피보나치 문제들을 풀면서 비슷한 유형들 여러 가지를 푸는데 상당히 재미있다. 이번 문제는 행렬 제곱을 이용한 큰 수의 피보나치 수를 구해서 최대공약수를 구하는 것이다. 이 문제는 각각 n과 m에 대해서 피보나치 수열을 구하고 그 수의 최대 공약수를 구해도 되지만 n과 m을 미리 최대공약수를 구한 뒤 그 수의 피보나치 수를 구해도 된다. #include #include using namespace std; using ll = unsigned long long; const..

www.acmicpc.net/problem/29812981번: 검문트럭을 타고 이동하던 상근이는 경찰의 검문을 받게 되었다. 경찰은 상근이가 운반하던 화물을 하나하나 모두 확인할 것이기 때문에, 검문하는데 엄청나게 오랜 시간이 걸린다. 상근이는 시간��www.acmicpc.netar 배열에 입력받은 수들을 정렬해주고어떤 수 ar[i] = 몫*나눈값+나머지 이므로 나머지를 처리해줘야 하니ar[i] - ar[i-1] = 나눈값(몫-몫2) + (나머지-나머지) 이다나눌 값들은 각각에 배열들에 대해 최대공약수를 구해서 그 최대공약수의 약수들로 나눠주면 같은 나머지가 출력된다. #include #include #include using namespace std; int GCD(int x, int y) { if (..