본문 바로가기

유클리드 호제법2

[Java] BOJ 6064 카잉 달력 문제 문제 링크 https://www.acmicpc.net/problem/6064최근에 ICPC 탐사대는 남아메리카의 잉카 제국이 놀라운 문명을 지닌 카잉 제국을 토대로 하여 세워졌다는 사실을 발견했다. 카잉 제국의 백성들은 특이한 달력을 사용한 것으로 알려져 있다. 그들은 M과 N보다 작거나 같은 두 개의 자연수 x, y를 가지고 각 년도를 와 같은 형식으로 표현하였다. 그들은 이 세상의 시초에 해당하는 첫 번째 해를 로 표현하고, 두 번째 해를 로 표현하였다. 의 다음 해를 표현한 것을 이라고 하자. 만일 x 같은 방식으로 만일 y 은 그들 달력의 마지막 해로서, 이 해에 세상의 종말이 도래한다는 예언이 전해 온다. 예를 들어, M = 10 이고 N = 12라고 하자. 첫 번째 해는 로 표현되고, 1.. 2024. 8. 25.

[Java] BOJ 2609 최대공약수와 최소공배수 문제 문제 링크 https://www.acmicpc.net/problem/2609두 개의 자연수를 입력받아 최대 공약수와 최소 공배수를 출력하는 프로그램을 작성하시오.첫째 줄에는 두 개의 자연수가 주어진다. 이 둘은 10,000이하의 자연수이며 사이에 한 칸의 공백이 주어진다.첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다.아이디어최대공약수와 최소공배수를 숫자를 일일이 사용하여 구할려고 하다가 공식이 있었던 것 같아서 문제풀기 전에 먼저 찾아봤었다.그 방법은 유클리드 호제법인데 유클리드 호제법이란 a를 b로 나눈 나머지 r로 b를 나눴을때 나온 나머지 r'이 0이면 그 r이 최대공약수라는 것이다. 만약 0으로 떨어지지 않는다면 a 자리에 b.. 2024. 7. 12.

이전 1 다음

최근글

인기글

공지사항

최근댓글

티스토리툴바