数论模板(个人模板)

基础函数:

// 最大公约数,欧几里得定理
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互质的数的个数

int eular(int n)
{
    int res = 1, i;
    for(i = 2; i * i < res; i ++)
    {
        if(n % i == 0)
        {
            n /= i;
            res *= (i - 1);
            while(n % i == 0)
                n /= i, res *= i;
        }
    }
    if(n > 1)
        res *= n - 1;
    return res;
}

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.排列组合

/**
 * 排列组合数(素数表示法)
 * 注意传入的数组先初始化为0
 * 复杂度:O(nlog(n)),n为素数个数
 */
// 全排列
// 参数: A(n), p[] 传出数的数组表示指针
// 返回值:结果包含的素数个数
int Arrangement(int n, int p[])
{
    int t, i;
    for(i = 0; i < num_prime && prime[i] <= n; i ++)
    {
        t = n;
        while(t)
            p[i] += t / prime[i], t /= prime[i];
    }
    return i;
}
// 排列
// 参数: A(m,n),m >= n , p[] 传出数的数组表示指针
// 返回值:结果包含的素数个数
int A_Cache[2][MAXP];//缓存项
int Arrangement_A(int m, int n, int p[])
{
    int i;
    ::memset(A_Cache, 0, sizeof(A_Cache));
    int r = Arrangement(m, A_Cache[0]);
    Arrangement(n, A_Cache[1]);
    for(i = 0; i < num_prime; i ++)
        p[i] = A_Cache[0][i] - A_Cache[1][i];
    return r;
}
// 组合
// 参数: C(m,n),m >= n , p[] 传出数的数组表示指针
// 返回值:结果包含的素数个数
int C_Cache[3][MAXP];//缓存项
int Combination(int m, int n, int p[])
{
    int i;
    memset(C_Cache, 0, sizeof(C_Cache));
    int r = Arrangement(m, C_Cache[0]);
    Arrangement(n, C_Cache[1]);
    Arrangement(m - n, C_Cache[2]);
    for(i = 0; i < num_prime; i ++)
        p[i] = C_Cache[0][i] - C_Cache[1][i] - C_Cache[2][i];
    return r;
}

// 取模计算:参数: mod为取模的值,其他参数同上
// 全排列取模
int Arrangement_Mod(int n, int p[], int mod)
{
    int res = 1;
    int i, r = Arrangement(n, p);
    for(i = 0; i < r; i ++)
        res = (res * PowerMod(prime[i], p[i], mod)) % mod;
    return res;
}
// 排列取模
int Arrangement_A_Mod(int m, int n, int p[], int mod)
{
    int res = 1;
    int i, r = Arrangement_A(m, n, p);
    for(i = 0; i < r; i ++)
        res = (res * PowerMod(prime[i], p[i], mod)) % mod;
    return res;
}
// 组合取模
int Combination_Mod(int m, int n, int p[], int mod)
{
    int res = 1;
    int i, r = Combination(m, n, p);
    for(i = 0; i < r; i ++)
        res = (res * PowerMod(prime[i], p[i], mod)) % mod;
    return res;
}

/**
 * 大组合数对素数取模
 * 复杂度: O(n),n素数大小
 */

// 大整数组合取模
const int MAXMOD = 10007;
int C_Map[MAXMOD + 1] = {0};
void BC_Init(int n, int mod)//初始化调用
{
    int i;
    C_Map[1] = 1;
    for(i = 2; i < n; ++ i)
        C_Map[i] = (C_Map[i - 1] * i) % mod;
}
int BC_Combination(int m, int n, int mod)
{
    int x, y;
    if(m < n)
        return 0;
    else
    {
        if(n == 0)
            return 1;
        int mm, nn;
        mm = C_Map[m];
        nn = (C_Map[n] * C_Map[m - n]) % mod;
        int shr = gcd(mm, nn);
        mm /= shr;
        nn /= shr;
        ext_gcd(nn, mod, x, y);
        return (x + mod) * mm % mod;//注意越界
    }
}
//调用的函数
int BN_Combination(int m, int n, int mod)
{
    int m_Num[50] = {0}, n_Num[50] = {0}, i, res = 1;
    //转换为mod进制数
    for(i = 0; m; i ++)
        m_Num[i] = m % mod, m /= mod;
    int t = i;
    for(i = 0; n; i ++)
        n_Num[i] = n % mod, n /= mod;
    for(i = t - 1; i >= 0; i --)
        res = (res * BC_Combination(m_Num[i], n_Num[i], mod)) % mod;//注意越界
    return res;
}

4.分数类+高斯消元

/**
 * 高斯消元和与之配合的分数类
 * 高斯消元复杂度O(n^3),n为未知数个数
 * #include <cmath>
 */

/**
 * 分数类(注意越界)
 */
struct mark
{
    int c, m;
    mark(){}
    mark(int x):c(x), m(1){}
    mark(int _c, int _m)
    {
        int d = gcd(::abs(_c), ::abs(_m));
        c = _c / d;
        m = _m / d;
        if(c < 0 && m < 0)
            c *= -1, m *= -1;
    }

    mark operator+(const mark &r) const
    {
        return mark(c * r.m + m * r.c, m * r.m);
    }

    mark operator-(const mark &r) const
    {
        return mark(c * r.m - m * r.c, m * r.m);
    }

    mark operator*(const mark &r) const
    {
        return mark(c * r.c, m * r.m);
    }

    mark operator/(const mark &r) const
    {
        return mark(c * r.m, m * r.c);
    }

    mark pow(int t)
    {
        mark tp = (*this);
        mark a = mark(1, 1);
        while(t > 0)
        {
            if(t & 1)
                a = a * tp;
            tp = tp * tp;
            t >>= 1;
        }
        return a;
    }

    bool operator==(const mark &r) const
    {
        return ((*this) - r).c == 0;
    }
    //其他判断类似
    bool operator<(const mark &r) const
    {
        mark rk = (*this) - r;
        return rk.c * rk.m < 0;//小心越界
    }
    bool operator>=(const mark &r) const
    {
        return !((*this) < r);//小心越界
    }
};

mark abs(const mark &x)
{
    return mark(::abs(x.c), ::abs(x.m));
}

/**
 * 高斯消元(求解:a[i][j] * x[j] = b[j])
 * 复杂度: O(n^3)
 * 可导入分数类(修改类型时修改zero函数,mark类型和abs函数即可)
 */
struct gauss_mat
{
    static const int maxn = 100;//最大未知数数量
    mark mat[maxn][maxn + 1];//增广矩阵
    mark x[maxn];//解集

    //浮点型和分数类型数据注意修改这里
    bool zero(const mark &x)
    {
        return x.c == 0;
    }

    gauss_mat(){}
    //构造sum{a[i][j] * x[j]} = b[i]
    gauss_mat(mark a[][maxn], mark b[], int _n)
    {
        for(int i = 0; i < _n; i ++)
        {
            for(int j = 0; j < _n; j ++)
                mat[i][j] = a[i][j];
            mat[i][_n] = b[i];
        }
    }

    //获取解
    mark& operator[](int p)
    {
        return x[p];
    }

    //交换行
    void swapR(int r1, int r2, int n)
    {
        for(int i = 0; i <= n; i ++)
        {
            mat[r1][i] = mat[r1][i] + mat[r2][i];
            mat[r2][i] = mat[r1][i] - mat[r2][i];
            mat[r1][i] = mat[r1][i] - mat[r2][i];
        }
    }

    //高斯消元(整数)
    //返回0为有无穷解或无解,返回1有唯一解并计算答案,返回-1无解
    bool gauss(int n)
    {
        int i, j, k, pj;
        for(i = 0; i < n; i ++)
        {
            pj = i;
            //注意类型
            mark p = mat[i][i];
            for(j = i + 1; j < n; j ++)
                if(::abs(p) < ::abs(mat[j][i]))
                    p = mat[j][i], pj = j;
            if(zero(p))
                return false;
            else if(i != pj )
                swapR(i, pj, n);
            for(j = i + 1; j < n; j ++)
            {
                /*
                //-----以下三选一-----
                //参数都是int(易越界)
                int d = gcd(::abs(mat[j][i]), ::abs(p));
                int lp = p / d, rp = mat[j][i] / d;
                d = (mat[j][i] * p < 0)? 1: -1;
                for(k = i; k <= n; k ++)
                    mat[j][k] = lp * mat[j][k] + d * rp * mat[i][k];
                //------int------

                //参数是double
                double d = mat[j][i] / p;
                for(k = i; k <= n; k ++)
                    mat[j][k] = mat[j][k] - d * mat[i][k];
                //------double------
                */
                //参数是mark(为了不易越界,整数建议用分数表示)
                //注意可以删除一些mark标签
                mark d = mat[j][i] / p;
                for(k = i; k <= n; k ++)
                    mat[j][k] = mat[j][k] - d * mat[i][k];
            }
        }

        for(i = n - 1; i >= 0; i --)
        {
            //注意能被整除,否则需要改变类型
            if(zero(mat[i][i]))
                return false;
            mark p = mat[i][i];
            mark sum = mat[i][n];
            for(j = i + 1; j < n; j ++)
                sum = sum -  mat[i][j] * x[j];
            x[i] = sum / p;
        }
        return true;
    }
};

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏GIS讲堂

用GeoTools实现shp+sld导出图片

23930
来自专栏mathor

LeetCode410. 分割数组的最大值

 这道题看着好像没什么思路,但其实可以利用二分法来做,二分法中的mid就是最终要返回的值,也就代表着子数组的和最小的值  我们首先还是设置左右区间,左区...

14530
来自专栏达摩兵的技术空间

经典面试题:数组去重

22110
来自专栏web前端教室

javascript 红皮高程(17)

按位操作符真是有头大的感觉,其实我也不太清楚哪里可以用到它。但即使不懂,也要先学会再说。 今天继续,按位或(OR), 它由一个竖线符号(|) 表示,同样也是操作...

200100
来自专栏Redis源码学习系列

Redis源码学习之字典

在字典结构体中,包含了一组字典函数(dictType),通过封装的方法处理对应的操作,通常在字典初始化的时候对其进行配置。

35910
来自专栏C语言及其他语言

[每日一题]C语言程序设计教程(第三版)课后习题7.1

题目描述 用简单素数筛选法求N以内的素数。 输入 N 输出 2~N的素数 样例输入 100 样例输出 2 3 5 7 11 13 17 19 23 29 31 ...

47050
来自专栏漫漫深度学习路

pytorch学习笔记(十二):详解 Module 类

Module 是 pytorch 提供的一个基类,每次我们要 搭建 自己的神经网络的时候都要继承这个类,继承这个类会使得我们 搭建网络的过程变得异常简单。 本文...

52960
来自专栏Crossin的编程教室

【Python 第28课】 字符串的分割

字符串和list之间有很多不得不说的事。比如有同学想要用python去自动抓取某个网页上的下载链接,那就需要对网页的代码进行处理。处理的过程中,免不了要在字符串...

34040
来自专栏蓝天

sed 学习笔记(转)

声明:这些代码只是为了学习和理解sed命令而为之,并不代表问题的唯一解或最佳解,希望各位拍砖

8520
来自专栏Golang语言社区

Golang精编100题

能力模型 级别模型初级 primary熟悉基本语法,能够看懂代码的意图; 在他人指导下能够完成用户故事的开发,编写的代码符合CleanCode规范;中级 int...

427110

扫码关注云+社区

领取腾讯云代金券