하수하따 록기장

문제 정수 B에 0보다 큰 정수인 N을 곱해 정수 A를 만들 수 있다면, A는 B의 배수이다. 당신은 두 수에 대하여 최소공배수를 구하는 프로그램을 작성 하는 것이 목표이다. 입력 한 줄에 두 정수 A와 B가 공백으로 분리되어 주어진다. 50%의 입력 중 A와 B는 1000(103)보다 작다. 다른 50%의 입력은 1000보다 크고 100000000(108)보다 작다. 추가: 큰 수 입력에 대하여 변수를 64비트 정수로 선언하시오. C/C++에서는 long long int를 사용하고, Java에서는 long을 사용하시오. 출력 A와 B의 최소공배수를 한 줄에 출력한다. #include using namespace std; int gcd(long long int a, long long int b){ // ..

이산수학 보강 수업에서 유클리드 알고리즘에 대해 배웠다. 1학년 때부터 계속 배웠던건데 이번으로 3번째 정도 들으니까 좀 알겠더라.. 유클리드 알고리즘(유클리드 호제법)이란 2개의 자연수의 최대공약수를 쉽게 알아낼 수 있는 알고리즘이다. 최대공약수란 두 정수를 나누어 떨어지게 하는 수 중 가장 큰 정수를 의미한다. 두 정수 A, B의 최대공약수 k를 구해보자 (A > B) A = B * q + r 이라고 할 수 있다. (q는 몫, r은 나머지) A와 B의 최대 공약수는 k이므로 A = k·A', B = k·B' 라고 하자. (A'과 B'은 서로소) 그러면 k·A' = ( k·B') * q + r 이다. 이때, r = k·A' - ( k·B') * q 라고 쓸 수 있다. r = k(A' - B'·q)이므로..