기본 콘텐츠로 건너뛰기

유클리드 호제법 (최대공약수)

유클리드 호제법(- 互除法, Euclidean algorithm)은 2개의 자연수 또는 정식(整式)의 최대공약수를 구하는 알고리즘의 하나이다.

호제법이란 말은 두 수가 서로(互) 상대방 수를 나누어(除)서 결국 원하는 수를 얻는 알고리즘을 나타낸다.

2개의 자연수(또는 정식) a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다.

이 성질에 따라, b를 r로 나눈 나머지 r'를 구하고, 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다.

이는 명시적으로 기술된 가장 오래된 알고리즘이다.

78696과 19332의 최대공약수를 구하면,


78696 ＝ 19332×4 ＋ 1368



19332 ＝ 1368×14 ＋ 180



1368 ＝ 180×7 ＋ 108



108 ＝ 72×1 ＋ 36



180 ＝ 108×1 + 72



72 ＝ 36×2




최대 공약수는 36













라벨:





























댓글











댓글 쓰기




















이 블로그의 인기 게시물





















11401 : 이항계수 3 (Dynamic Programming, Divide and Conquer) [C++]




























 1번, 2번 문제들과 확연히 차이나는 입력의 범위. 400만 !     DP를 사용해서 풀 수 없는 문제이다 . 하지만 DP가 쓰이긴 한다!     수학은 너무 어렵다. 곱셈의 역원을 공부해보다가 모르겠어서 도움을 구했다.     왜 곱셈의 역원을 구해야하는가?     N! / (K! * (N-K)!) 에서 K! * (N-K)! 의 역원을 구해야 하기 때문!     곱셈의 역원을 구하는 정리인 페르마의 소정리를 이용하면       p가 1000000007 이지만 분할 정복을 이용한 제곱 수 계산 덕분에 logP 시간 소요.     분할 정복을 이용한 제곱 수 계산은 계속 써먹을 것 같아서 따로 올려놓았다.     DP가 쓰이는 부분은 구해준 400만의 역원을 바탕으로 모든 역원을 구하는 부분이다.     그러므로 총 시간 소요는 O(N+LogP)     long  long  BinomialCoefficient :: GetNum ( int  N ,  int  K )  {      this - > Factorial [ 1 ]  =  1 ;      for  ( int  i =  2 ;  i < =  4000000 ;  i + + )          this - > Factorial [ i ]  =  ( this - > Factorial [ i -  1 ]  *  i )  %  P ;                       this - > Invert [ 4000000 ]  =  this - > Pow_DC ( this - > Factorial [ 4000000 ] ,  P -  2 ) ;      for  ( int  i =  4000000  -  1 ;  i >  0 ;  i - - )           this - > Invert [ i ]  =  ( this - > Invert [ i +  1 ]  *  ( i +  1 ) )  %  P ;            if  ( N = =  K | |  K = ...




















댓글 쓰기









자세한 내용 보기





























1978 : 소수 찾기 [C++]




























# include < iostream >  # include < vector >   using  namespace  std ;   int  main ( )  {   cin . tie ( NULL ) ;    vector < int >  Primes ;    Primes . push_back ( 2 ) ;   Primes . push_back ( 3 ) ;   for  ( int  i =  4 ;  i <  1000 ;  i + + )   {    bool  IsPrime =  true ;     if  ( i %  2  = =  0  | |  i %  3  = =  0 )     continue ;    for  ( int  j =  4 ;  j <  i ;  j + + )    {     if  ( i %  j = =  0 )     {      IsPrime =  false ;      break ;     }    }     if  ( IsPrime )     Primes . push_back ( i ) ;   }    int  N ,  Count =  0 ;   cin  > >  N ;    for  ( int  i =  0 ;  i <  N ;  i + + )   {    int  Input ;    cin  > >  Input ;     for  ( int  j =  0 ;  j <  Primes . size ( ) ;  j + + )     if  ( Input = =  Primes [ j ] )      Count + + ;   }    cout  < <  Count < <  " \n " ;    return  0 ;  }  




















댓글 쓰기









자세한 내용 보기