<div>lehmer_gcd() 코드는 온라인에 있던 파이썬 코드 참조했습니다. 이해하는데 많은 시간이 걸렸어요.</div> <div>쓰실분들은 라이브러리처럼 쓰시길 바랍니다</div> <div><br></div> <div>#include <iostream></div> <div>#include <vector></div> <div>#include <algorithm></div> <div>#include <cmath></div> <div>using namespace std;</div> <div><br></div> <div>typedef long long ll;</div> <div><br></div> <div>ll gcd(ll a, ll b) {</div> <div> if(b>a) return gcd(b, a);</div> <div> if(b==0) return a;</div> <div> if(a%2==0 && b%2==0) return 2*gcd(a/2, b/2);</div> <div> if(a%2==0 && b%2==1) return gcd(a/2, b);</div> <div> if(a%2==1 && b%2==0) return gcd(a, b/2);</div> <div> return gcd((a-b)/2, b);</div> <div>}</div> <div><br></div> <div>ll DIGIT_BITS=30;</div> <div>ll BASE = 1 << DIGIT_BITS;</div> <div><br></div> <div>ll nbits(ll n) {</div> <div> return floor(log2(n))+1;</div> <div>}</div> <div><br></div> <div>ll lehmer_gcd(ll a, ll b) {</div> <div> if(a<b) return lehmer_gcd(b, a);</div> <div> while(b >= BASE) {</div> <div> ll push = nbits(a) - DIGIT_BITS;</div> <div> ll x = a >> push;</div> <div> ll y = b >> push;</div> <div> ll A=1, B=0, C=0, D=1;</div> <div> while(1) {</div> <div> if(y+C==0 || y+D==0) break;</div> <div> ll q = (x+A) / (y+C);</div> <div> if(q!=(x+B)/(y+D)) break;</div> <div> ll tempA=A, tempB=B, tempx=x;</div> <div> A=C; B=D; x=y;</div> <div> C=tempA-q*C; D=tempB-q*D; y=tempx-q*y;</div> <div> }</div> <div> if(B) {</div> <div> ll tempa = a;</div> <div> a = A*a + B*b;</div> <div> b = C*tempa + D*b;</div> <div> }</div> <div> else {</div> <div> ll tempa = a;</div> <div> a = b;</div> <div> b = tempa % b;</div> <div> }</div> <div> }</div> <div> return gcd(a, b);</div> <div>}</div> <div><br></div> <div>ll manygcd(vector<ll>& v) {</div> <div> int i;</div> <div> if(v.size()==1) return v[0];</div> <div> ll ans = gcd(v[0], v[1]);</div> <div> for(i=2; i<v.size(); i++) {</div> <div> ans = lehmer_gcd(ans, v[i]);</div> <div> }</div> <div> return ans;</div> <div>}</div>
댓글 분란 또는 분쟁 때문에 전체 댓글이 블라인드 처리되었습니다.