最大公约数

欧几里得算法

int gcd(int x, int y) {
    return y == 0 ? x : gcd(y, x % y);
}

扩展欧几里得算法

求 ax+by=c 的解以及逆元（a,b,c>0,c=gcd(a,b)）

// 返回 d=gcd(a,b); 和对应于等式 ax+by=d 中的 x,y;
int exgcd(int a, int b, int &x, int &y) {
    if (b == 0) {
        x = 1; y = 0;
        return a;
    }
    int gcd = exgcd(b, a % b, x, y);
    int t = x; x = y;
    y = t - a / b * y;
    return gcd;
}

不需要求gcd时：

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

一道例题：sgu106

同余方程求解

问题：

给出同余方程：cx \equiv a \pmod p，要求转化成 x \equiv a \pmod b 的形式。

// cx = a (mod p) ==> x = first (mod second)
// 事先进行 c %= p, a %= p 的操作；判断 c = 0 的特殊情况。
pair<ll, ll> get_equation(ll c, ll a, ll p) {
    ll x = 0, y = 0;
    ll gcd = exgcd(c, p, x, y), mod = p / gcd;
    if (a % gcd) {
        return make_pair(-1, -1);
    }
    x = mul(x, (a / gcd), mod);
    x = (x + mod) % mod;
    return make_pair(x, mod);
}

裴蜀定理

设 a,b 是不全为零的整数，则存在整数 x,y , 使得 ax+by=gcd(a,b) .

例题：CF510D Fox And Jumping

题目大意

给出 n 张卡片，分别有 l_i 和 c_i。在一条无限长的纸带上，你可以选择花 c_i 的钱来购买卡片 i，从此以后可以向左或向右跳 l_i 个单位。问你至少花多少元钱才能够跳到纸带上全部位置。若不行，输出 -1。

分析

由裴蜀定理可知，问题转化为：选取每个数有一定的代价，选取一些数使得它们 gcd=1，最小化代价。我们可以用map来转移dp，开一维滚动数组。

#include <bits/stdc++.h>
using namespace std;
const int N = 305;
int n, l[N], c[N];

int o;
map<int, int> mp[2];
int gcd(int x, int y) {
    return y == 0 ? x : gcd(y, x % y);
}

int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) scanf("%d", &l[i]);
    for(int i = 1; i <= n; i++) scanf("%d", &c[i]);
    mp[0][0] = 0;
    for (int i = 1; i <= n; i++) {
        o ^= 1;
        for (auto x : mp[o ^ 1]) {
            int tmp = gcd(l[i], x.first);
            if(mp[o][tmp]) mp[o][tmp] = min(mp[o][tmp], x.second + c[i]);
            else mp[o][tmp] = x.second + c[i];
            if(mp[o][x.first])mp[o][x.first] = min(mp[o][x.first], x.second);
            else mp[o][x.first] = x.second;
        }
    }
    if(mp[o][1]) printf("%d\n", mp[o][1]);
    else puts("-1");
    return 0;
}

基于值域预处理的快速GCD算法

const int M = 1e6;
const int T = 1e3;

struct Fast_GCD {
    int pre[T + 2][T + 2];
    int fac[M + 2][3];
    bool isp[M + 2];
    int pri[M / 10], tot;

    void init() {
        fac[1][0] = fac[1][1] = fac[1][2] = 1;
        for (int i = 2; i <= M; ++i) {
            if (!isp[i]) {
                fac[i][0] = fac[i][1] = 1;
                fac[i][2] = i;
                pri[++tot] = i;
            }
            for (int j = 1; pri[j] * i <= M; ++j) {
                int tmp = pri[j] * i;
                isp[tmp] = true;
                fac[tmp][0] = fac[i][0] * pri[j];
                fac[tmp][1] = fac[i][1];
                fac[tmp][2] = fac[i][2];
                if (fac[tmp][0] > fac[tmp][1]) {
                    fac[tmp][0] ^= fac[tmp][1] ^= fac[tmp][0] ^= fac[tmp][1];
                }
                if (fac[tmp][1] > fac[tmp][2]) {
                    fac[tmp][1] ^= fac[tmp][2] ^= fac[tmp][1] ^= fac[tmp][2];
                }
                if (i % pri[j] == 0) {
                    break;
                }
            }
        }
        for (int i = 0; i <= T; ++i) {
            pre[0][i] = pre[i][0] = i;
        }
        for (int i = 1; i <= T; ++i) {
            for (int j = 1; j <= i; ++j) {
                pre[i][j] = pre[j][i] = pre[j][i % j];
            }
        }
    }

    int gcd(int a, int b) {
        int ans = 1;
        for (int i = 0, tmp; i < 3; ++i) {
            tmp = (fac[a][i] > T) ?
                  (b % fac[a][i] ? 1 : fac[a][i]) :
                  pre[fac[a][i]][b % fac[a][i]];
            b /= tmp;
            ans *= tmp;
        }
        return ans;
    }
}mygcd;

快速幂

普通快速幂

int ksm(int a, int b) {
    int ret = 1;
    for (; b; b >>= 1, a = 1LL * a * a % P) {
        if (b & 1) ret = 1LL * ret * a % P;
    }
    return ret;
}

O(1)光速幂

例题：2019南昌网络赛H

求\frac{\sqrt{17}}{17}\left((\frac{3+\sqrt{17}}{2})^n-(\frac{3-\sqrt{17}}{2})^n\right),共10^7组询问，n\le 10^{18}。

思路：
适用于同一底数要算不同指数多次快速幂。先预处理出三个底数tmp0, tmp1, tmp2。再利用BSGS的思想，预处理出tmp1、tmp2的2^{16}以内次方；再处理Great Step。这样可以省去快速幂的一个log的复杂度。

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int P = 998244353;
const int sqrt17 = 473844410, inv17 = 939524097, inv2 = 499122177;
int tmp0, tmp1, tmp2;
const int MAXN = 65536;
int ans1[MAXN + 50], ans2[MAXN + 50]; // tmp1和tmp2的k次方
int pans1[MAXN + 50], pans2[MAXN + 50]; //(tmp1^65536)的k次方
int Q; ll N;

void init() {
    tmp0 = 1LL * sqrt17 * inv17 % P;
    tmp1 = 1LL * (3 + sqrt17) * inv2 % P;
    tmp2 = 1LL * (3 - sqrt17 + P) * inv2 % P;
    ans1[0] = ans2[0] = 1;
    for (int i = 1; i <= MAXN; i++) {
        ans1[i] = 1LL * ans1[i-1] * tmp1 % P;
        ans2[i] = 1LL * ans2[i-1] * tmp2 % P;
    }
    pans1[0] = pans2[0] = 1;
    int ptmp2 = ans1[MAXN], ptmp3 = ans2[MAXN];
    for(int i = 1; i <= MAXN; i++) {
        pans1[i] = 1LL * pans1[i-1] * ptmp2 % P;
        pans2[i] = 1LL * pans2[i-1] * ptmp3 % P;
    }
}
int ksm1(ll b) {
    if(b > P) b %= P - 1;
    if(b <= MAXN) return ans1[b];
    int tmp = b & 65535, ret = ans1[tmp];
    b >>= 16;
    return 1LL * pans1[b] * ret % P;
}
int ksm2(ll b) {
    if(b > P) b %= P - 1;
    if(b <= MAXN) return ans2[b];
    int tmp = b & 65535, ret = ans2[tmp];
    b >>= 16;
    return 1LL * pans2[b] * ret % P;
}

inline int query(ll x) {
    return 1LL * tmp0 * (ksm1(x) - ksm2(x) + P) % P;
}
void work() {
    ll a = 0, n = N;
    int ans = 0;
    for (int i = 1; i <= Q; i++) {
        a = query(n); n ^= (a * a); ans ^= a;
    }
    printf("%d\n", ans);
}

int main() {
    scanf("%d%lld", &Q, &N);
    init(); work();
    return 0;
}

求逆元

费马小定理

int ksm(int a, int b) {
    int ret = 1;
    for (; b; b >>= 1, a = 1LL * a * a % P) {
        if (b & 1) {
            ret = 1LL * ret * a % P;
        }
    }
    return ret;
}
int ni(int a) {
    return ksm(a, P - 2);
}

扩展欧几里得

void exgcd(int a, int b, int &x, int &y) {
    if (b == 0) {
        x = 1; y = 0;
    }
    else {
        exgcd(b, a % b, y, x);
        y -= a / b * x;
    }
}
int ni(int a, int p) {
    int x = 0, y = 0;
    exgcd(a, p, x, y);
    return (x % p + p) % p;
}

线性预处理逆元

设 p\div a=x \cdots\cdots y，即 p=ax+y.

\begin{aligned}
&\therefore ax+y\equiv 0\ (mod\ p) \cr
&\therefore x+ya^{-1}\equiv 0\ (mod\ p) \cr
&\therefore a^{-1}\equiv\frac{-x}{y} \ (mod\ p)
\end{aligned}

int ni[N];
void init() {
    ni[1] = 1;
    for(int i = 2; i <= n; i++) {
        ni[i] = 1LL * (P - P / i) * ni[P % i] % P;
    }
}