Mod Inverse

コードについての説明

$\mathbb{Z} / p \mathbb{Z}$ 上で $p$ と互いに素である $a$ の逆元を拡張ユークリッドの互除法を用いて計算するアルゴリズム.
"$a$ と $p$ が互いに素 $\Leftrightarrow$ $\mathbb{Z} / p \mathbb{Z}$ 上で $a$ の逆元が存在する" が成り立つことに注意する.

(関数)
$mod_inverse(a, p)$ : $\mathbb{Z} / p \mathbb{Z}$ 上で $a$ の逆元を求める(ただし $a$ と $p$ は互いに素とする).

時間計算量: $\O (\log a)$

コード

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

int mod_inverse(int a, int p)
{
    int x, y;
    extgcd(a, p, x, y);
    return (p + x % p) % p;
}

verify 用の問題

省略