Si_Yue小屋
0%

GCD

发表于 分类于

\((a,b)=(b,a\,mod\,b)\)

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
//递归
LL gcd1(LL a,LL b){
    if(b==0)return a;
    return gcd1(b,a%b);
}

//迭代
LL gcd2(LL a,LL b){
    while(b){
        LL tmp=a;
        a=b;
        b=tmp%b;
    }
    return a;
}

//stein算法
LL gcd3(LL a,LL b){
    if(a==b)return a;
    else if(a%2==0&&b%2==0){
        return 2*gcd3(a/2,b/2);
    }else if(a%2==0){
        return gcd3(a/2,b);
    }
    if(a<b)swap(a,b);
    return gcd3(a-b,b);
}

//多个数的gcd
LL getgcd(queue<LL> q){
    while(q.size()!=1){
        int x=q.front();
        q.pop();
        int y=q.front();
        q.pop();
        q.push(gcd1(x,y));
    }
    return q.front();
}