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