반응형 유클리드 호제법2 [C/C++] 백준 #1850 최대공약수(수학) 이번문제는 문제를 살짝 꼬았지만, 결국 최대 공약수를 구하는 문제입니다. 유클리드 호제법을 이해하고 있다면, 이 문제를 쉽게 풀 수 있습니다. 유클리드 호제법에서 큰수에서 작은수로 나눈 나머지를 가지고 우리는 최대 공약수를 구할 수 있습니다. \[ g = gcd(a, b) = gcd(a-b, b) \] 형태가 성립하기 때문이죠. 위식에서는 뺄셈을 했지만, 나눈 나머지를 해도 됩니다. a 개의 연속된 1이 있는 숫자와 b개의 연속된 1이 있는 숫자 역시 마찬가지죠. \(a \gt b\)라고 한다면, a개의 연속된 1이 있는 숫자를 b개의 연속된 1이 있는 숫자로 나눈 나머지는 a를 b로 나눈 나머지의 개수만큼 1이 연속된 수가 됩니다. 예를 들어서 5개의 1이 연속된 11111 과 3개의 1이 연속된 11.. 2022. 10. 25. 소수 판별하기 우리가 컴퓨터에서 합당한 시간안에 결과를 찾을 수 있는 것은 과연 어느정도의 시간일까라는 생각을 많이 해봅니다. 암호학이라고 한다면, 적어도 100년? 아니면 그 이상일 수도 있겠다는 생각도 하죠. 주어진 수가 소수인지 아닌지, 판별하는 방법은 고전적인 방법에서부터 정수론에 기초한 방법까지 다양하게 있습니다. 소수판별법은 암호학에서 아주 중요합니다. 실제 소수판별을 쉽게 하는 방법이 있다면, 암호 해독도 더 쉬워집니다. 제일먼저 유클리드 호제법을 응용한 방법입니다. [유클리드 호제법을 이용한 소수 판별] bool isPrimeBF(_int64 n) { if( n%2 == 0 ) return false; for( unsigned __int64 r = 3 ; r*r >=1 ) ; for( int i = 0 .. 2014. 10. 7. 이전 1 다음 728x90
