최대공약수 검색 결과

해당 글 4건
백준 시철이가 사랑한 수식을 브루트 포스로 검수한 썰

어느덧 500번째 글입니다. 그냥 정보글은 시시하니, 대회 검수 썰을 풀어보도록 하겠습니다. SUAPC를 검수하면서 신경을 썼던 것 중 하나는, 대회에 출제된 20940번 문제였습니다. 대회에 출제된 문제 중에 난이도가 높은 그룹에 속할 것이라고 예상했고, 실제로 그렇게 되었습니다. 이 문제를 검수할 때 세웠던 원칙 중 하나는 브루트 포스로 검증을 해 볼만한 사이즈가 되면, 검증을 해 보자는 것이였습니다. 100만이면 모르겠지만, 50만이면 해 볼 만 했습니다. 잘 돌리면 1시간 정도에 해결을 할 수 있었기 때문입니다. 이 문제의 초기 조건은 N은 [1, 50만], K는 10^9+7이였습니다. 브루트 포스로 돌릴 만 합니다. 그런데, 이걸 그냥 브루트 포스로 돌리기에는? N이 대충 50만. 50만의 제곱..
자료알고/알고리즘 2021. 5. 21. 04:02
항등식으로 구현체를 외울 수 있는 확장 유클리드 알고리즘

안녕하세요. 백준 chogahui05입니다. RSA 알고리즘을 알기 위해서, 알아야 하는 것이 몇 가지 있는데요. 그 중 하나인 확장 유클리드 알고리즘을 알아보겠습니다. 사실 CRT라던지, 페르마의 소정리도 알아두면 좋기는 합니다. 이게 무엇을 구하는 것인지 알아보겠습니다. a와 b가 매우 큰 수일 때, 이 값은 어떻게 구하는 것이 좋을까요? 일단, gcd(a,b)의 값이 k이고, k값이 1이 아니라고 해 봅시다. 그러면, a = ka', b = kb'으로 다시 쓸 수 있습니다. gcd(a,b)값이 k이므로, a'과 b'도 정수입니다. x와 y가 정수라면 a'x + b'y도 정수입니다. 그러면, 1은 k의 배수여야 합니다. 그렇지 않습니다. 따라서, a와 b의 최대 공약수가 1이 아니라면, ax + by..
자료알고/알고리즘 2020. 4. 9. 23:42
백준 11691 lcm(i,j) : lcm과 gcd의 관계를 이용한 역발상이 필요하다.

오늘은 2019년 마지막 날이니, 마지막 날을 장식할 만한 포스트를 작성하도록 하겠습니다. 아래 수식의 결과 값을 10억 7로 나눈 나머지는 얼마일까요? 단, n은 2이상, 10^6 이하 자연수입니다. n = 10^6이면 대충 O(n)이나, O(128n)에 돌려도 무난할 복잡도입니다. 이것이 생각보다 꽤 큰 힌트 중 하나입니다. 먼저, 최대 공약수에 대한 관점을 비틀어 봅시다. a와 b의 최대 공약수가 g였다고 해 봅시다. 이걸 P라고 합시다. 그러면 위 수식이 성립합니다. 그런데 정말 그럴까요? 위 수식을 Q라고 해 봅시다. 만약에, gcd(a/g,b/g)의 값이 c이고, 이 값이 1이 아니라면, gcd(a,b)의 값은 gc가 됩니다. c가 1이 아니므로, gc의 값은 g가 아닙니다. 즉, not Q이..
자료알고/알고리즘 2019. 12. 31. 21:57
최대공약수 최소공배수 알고리즘 : 짧은 코드 이해해 봅시다.

오늘은 간단하게, 최대 공약수와 최소 공배수를 구하는 알고리즘을 알아보도록 하겠습니다. 먼저 a와 b의 최대 공약수란, a와 b를 동시에 나누어 떨어지게 하는 최댓값을 의미해요. 예를 들어서 a가 6이고 b가 3이라면 3이 gcd가 됩니다. 그렇다면 가장 간단한 알고리즘을 생각해 볼 수 있습니다. a와 b의 최솟값을 r이라고 해 봅시다. r부터 1까지 계속 a와 b를 나누어 보면서, 만약에 두 수를 동시에 나누는 수가 있다면 break를 걸어버리는 겁니다. 사실, 이러한 방법은 꽤 효과적일 수 있습니다. 그런데 a = 20억, b = 10억 7 정도가 된다고 하면, 수행 시간이 상당히 길어질 겁니다. 왜냐하면 b는 소수이기 때문입니다. b를 나누는 수는 1과 10억 7밖에 없는데, 20억을 나누는 수는 ..
자료알고/알고리즘 2019. 8. 7. 17:50