数论入门——（1）

本文所有的证明均参见OI Wiki

欧几里德定理

证明参见OI Wiki

$$gcd(a,b)=gcd(b,a \; mod \; b)$$

利用这一重要的定理，容易发现这样的操作递归到最后一定会得到一个\(gcd(m,0)\)，此时值为m，我们就可以利用递归法快速地求出\(gcd(a,b)\)

int gcd(int a, int b)
{
    if (b == 0)
        return a;
    return gcd(b, a % b);
}

裴蜀定理

证明参见OI Wiki

裴蜀定理通常用来求解二元不定方程的解

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

而求解这样的方程通常使用扩展欧几里德定理

扩展欧几里德定理

证明参见OI Wiki

ll exgcd(ll a, ll b, ll &x, ll &y)
{
    if (b == 0)
    {
        x = 1;
        y = 0;
        return a; //一组特解
    }

    ll g = exgcd(b, a % b, y, x);
    y -= (a / b) * x;
    return g;
}

同余定理

\(a≡b(mod \; m)\)

乘法逆元

扩展欧几里德求逆元

例题：洛谷P1082 同余方程

/*
 * @Author: Gehrychiang
 * @LastEditTime: 2020-04-19 13:37:39
 * @Website: www.yilantingfeng.site
 * @E-mail: gehrychiang@aliyun.com
 */
//#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll exgcd(ll a, ll b, ll &x, ll &y) //x即为a相对模b的逆元
{
    if (b == 0)
    {
        x = 1;
        y = 0;
        return a;
    }
    ll g = exgcd(b, a % b, y, x);
    y -= (a / b) * x;
    return g;
}
int main()
{
    //freopen("","r",stdin);
    //freopen("","w",stdout);
    ll x, y;
    ll a, b;
    cin >> a >> b;
    exgcd(a, b, x, y);
    cout << (x + b) % b << endl; //会存在负数
    //fclose(stdin);
    //fclose(stdout);
    return 0;
}

小费马定理求逆元

\(x ≡ a^{b-2}(mod \; b)\) \(x\)为\(a\)相对于\(b\)的逆元

（仅限于\(b\)为质数，且\(a,b\)互质才可用）

证明请参见OI Wiki

快速幂请见快速幂（模板）

线性筛求逆元

推导请见OI Wiki

\(inv[p]=-(p/i * inv[p \; mod \; i]) \; mod \; p\)

例题：洛谷P3811 乘法逆元

/*
 * @Author: Gehrychiang
 * @LastEditTime: 2020-04-19 13:46:57
 * @Website: www.yilantingfeng.site
 * @E-mail: gehrychiang@aliyun.com
 */
//#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
long long inv[3000005];
int main()
{
    //freopen("","r",stdin);
    //freopen("", "w", stdout);
    long long n, p;
    scanf("%lld %lld", &n, &p);
    inv[1] = 1;
    printf("%lld\n", inv[1]);
    for (int i = 2; i <= n; i++)
    {
        inv[i] = p - (p / i * inv[p % i]) % p; //此处为公式加上一个p再模p是为了保证不出现负解
        printf("%lld\n", inv[i]);
    }
    //fclose(stdin);
    //fclose(stdout);
    return 0;
}

Lucas定理

这是一个用来求大组合数取模的算法

ATTENTION：只适用于模数较小(1e6)时，因为过大时逆元运算次数过多，时间复杂度较大

证明参见OI Wiki

$$lucas(n,m)=(C^{m \; mod \; p}_{n \; mod \; p}*lucas(n / p, n / p)) \; mod \; p$$

（实质是将大组合数取模拆分小组合数取模）而小组合数的计算用乘法逆元实现即可

例题：洛谷P3807 卢卡斯定理

/*
 * @Author: Gehrychiang
 * @LastEditTime: 2020-04-19 13:54:55
 * @Website: www.yilantingfeng.site
 * @E-mail: gehrychiang@aliyun.com
 */
#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll fastMul(ll a, ll b, ll mod)
{
    ll res = 0;
    while (b)
    {
        if (b & 1)
        {
            res = (res + a) % mod;
        }
        a = (a + a) % mod;
        b >>= 1;
    }
    return res;
}
ll fastPowMod(ll a, ll n, ll mod)
{
    if (n == 0 && a != 0)
        return 1;
    if (n != 0 && a == 0)
        return 0;
    ll base = a;
    ll res = 1;
    while (n)
    {
        if (n & 1)
        {
            res = fastMul(res, base, mod);
        }
        base = fastMul(base, base, mod);
        n >>= 1;
    }
    return res % mod;
}
//费马小定理求逆元
ll C(ll n, ll m, ll p) //实质
{
    if (n < m)
    {
        return 0;
    }
    if (m == 0)
    {
        return 1;
    }
    ll a = n - m + 1, b = 1;
    for (int i = 1; i < m; i++)
    {
        a = fastMul(a, n - m + 1 + i, p);
        b = fastMul(b, 1 + i, p);
    }
    return fastMul(a, fastPowMod(b, p - 2, p), p); //费马小定理法
}

ll lucas(ll n, ll m, ll p) //实质还是不断调用小费马定理求逆元去搞组合数
{
    if (n < m)
    {
        return 0;
    }
    if (m == 0) //跳出条件
    {
        return 1;
    }
    else
    {
        return (C(n % p, m % p, p) * lucas(n / p, m / p, p));
    }
}

int main()
{
    //freopen("","r",stdin);
    //freopen("","w",stdout);
    int t;
    scanf("%d", &t);
    while (t--)
    {
        int n, m, p;
        scanf("%d %d %d", &n, &m, &p);
        cout << lucas(n + m, min(m, n), p) % p << endl;
    }
    //fclose(stdin);
    //fclose(stdout);
    return 0;
}

作为对照还有一类题目他同样是求大组合数取模但是因为模数较大不适于用lucas定理求解，故预处理阶乘及阶乘逆元直接套公式求解

例题：nefu 1196

题目很简单就是要输出\(C^{n-1}_{m+n-2} \; mod \; 1e9+7\) ，但是因为模数大，我们不适于使用lucas来做

/*
 * @Author: Gehrychiang
 * @LastEditTime: 2020-04-19 11:51:45
 * @Website: www.yilantingfeng.site
 * @E-mail: gehrychiang@aliyun.com
 */
//平平无奇的预处理优化
#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
long long fac[2000005];
long long inv[2000005]; //inv[i]存储fac[i]的逆元
const long long mod = 1e9 + 7;
long long fastMul(long long a, long long b, long long mod)
{
    long long res = 0;
    while (b)
    {
        if (b & 1)
        {
            res = (res + a) % mod;
        }
        a = (a + a) % mod;
        b >>= 1;
    }
    return res;
}

long long fastPowMod(long long a, long long n, long long mod)
{
    if (n == 0 && a != 0)
        return 1;
    if (n != 0 && a == 0)
        return 0;
    long long base = a;
    long long res = 1;
    while (n)
    {
        if (n & 1)
        {
            res = fastMul(res, base, mod);
        }
        base = fastMul(base, base, mod);
        n >>= 1;
    }
    return res % mod;
}
void init()
{
    fac[0] = 1;
    for (int i = 1; i <= 2000000; i++)
    {
        fac[i] = (fac[i - 1] * i) % mod;
    }
    inv[2000000] = fastPowMod(fac[2000000], mod - 2, mod);
    for (int i = 2000000 - 1; i >= 0; i--)
    {
        inv[i] = ((i + 1) * inv[i + 1]) % mod;
    }
}
long long C(long long n, long long m)
{
    return ((fac[n] * inv[m]) % mod * inv[n - m]) % mod;
}
int main()
{
    //freopen("","r",stdin);
    //freopen("","w",stdout);
    init();
    int a, b;
    while (cin >> a >> b)
    {
        cout << C(a + b - 2, min(a - 1, b - 1)) << endl;
    }
    //fclose(stdin);
    //fclose(stdout);
    return 0;
}