数论模板（个人模板）

基础函数:

// 最大公约数,欧几里得定理
int gcd(int a, int b)
{
    return b?gcd(b, a % b): a;
}
// 拓展欧几里得定理
// 求解ax + by = gcd(a,b)
int ext_gcd(int a, int b, int &x, int &y)
{
    int tmp, ret;
    if(!b)
    {
        x = 1;
        y = 0;
        return a;
    }
    ret = ext_gcd(b, a % b, x, y);
    tmp = x;
    x = y;
    y = tmp - (a / b) * y;
    return ret;
}
//交换数值
void swap(int &a, int &b)
{
    a ^= b ^= a ^= b;
}

/**
 * a的b次方Mod c
 * 参数为整数
 * 使用时注意修改类型
 */
int PowerMod(int a, int b, int c)
{
    int tp = 1;
    while (b)
    {
        if (b & 1)
            tp = (tp * a) % c;
        a = (a * a) % c;
        b >>= 1;
    }
    return tp;
}

1.欧拉函数

Ψ（n） = 小于n且与n互质的数的个数

2.欧拉定理

若a与n互质（即GCD（a，n） = 1），则a^Ψ（n） = 1 （mod n）a^{\varphi(n)} \equiv 1 \pmod n

欧拉函数的一个定理：Ψ（n）= n – sum{Ψ（x）| 其中 n % x == 0}

3.排列组合

4.分数类+高斯消元

PreviousPOJ PKU 2826 An Easy Problem?! 解题报告Next简易四则运算(ACM个人模板)

Last updated

Was this helpful?