Next Nest

wusa!~(•㉨•)

「轉載】張 正錦 菌給的模板 V 數論數學

发表于 Valine：

第五輯 數論數學

  • 最大公約數(gcd)
  • 擴展Euclidean
  • 快速冪

GCD (Greatest Common Divisor)

C++
1
2
3
4
5
int Gcd(int a, int b)
{
    if(b==0) return a;
    return Gcd(b,a%b);
}

Ex-GCD (Extended Euclidean)

C++
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
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<string.h>
#include<queue>

using namespace std;

int x,y;

int exgcd(int a, int b, int &x, int &y)
{
    if(b == 0)
    {
        x = 1, y = 0;
        return a;
    }
    int g = exgcd(b,a%b,y,x);
    y -= a/b*x;
    return g;
}

int a,b;

int main()
{
    cin >> a >> b;
    exgcd(a,b,x,y);
    x = (x+b)%b;//最小正整数解 
    cout << x;
    return 0;
}

Binary Exponentiation

其實是二進制取冪，也稱平方法。

  • zzj提供的非遞歸方案 (mod p 意義下取冪)

    C++
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    int quick_power(int a, int b, int p)
    {
        int ans = 1;
        while(b)
        {
            if(b&1) ans = ans*a%p;
            a = a*a%p;
            b >>= 1;
        }
        return ans;
    }

  • OI-Wiki1上的遞歸實現

    C++
    1
    2
    3
    4
    5
    6
    7
    8
    long long binpow(long long a, long long b) {
        if (b == 0) return 1;
        long long res = binpow(a, b / 2);
        if (b % 2)
            return res * res * a;
        else
            return res * res;
        }

  • OI-Wiki上的非遞歸實現

    C++
    1
    2
    3
    4
    5
    6
    7
    8
    9
    long long binpow(long long a, long long b) {
        long long res = 1;
        while (b > 0) {
            if (b & 1) res = res * a;
            a = a * a;
            b >>= 1;
        }
        return res;
    }

References

1. OI-Wiki 章節 快速冪 ↩