一些关于数论这一章节的感悟

一.质数

1.试除法判断单个数是否为质数

2.唯一分解定理：任何一个大于1的整数都可以分解成x=p1^x1 * p2^x2 * … * pn^xn,其中，p1<p2<…<pk皆素数

分解质因数：

void divide(int x)
{
    for(int i=2;i<=x/i;i++)
    {
        if(x%i==0)
        {
            int res=0;
            while(x%i==0)
            {
                x/=i;
                res++;
            }
            cout<<i<<" "<<res<<endl;
        }

    }
    if(x>1)cout<<x<<" 1"<<endl;
}//为什么质因数的范围是sqrt（n），反证如果两个质因数都>=sqrt（n）那个这个数一定大于n，矛盾。所以仅仅会存在一个大于等于sqrt（n）的数

3.筛法求范围内的所有质数

其中包括埃式筛和线性筛，后者的时间复杂度更低

 void get_primes(int n)
{
    for (int i = 2; i <= n; i ++ )
    {
        if (st[i]) {
            primes[cnt ++ ] = i;
            for (int j = i + i; j <= n; j += i)
                st[j] = true;
        }
    }//如果i为质数就筛掉每一个i的倍数
}//时间复杂度为O(n log log n)


 void get_primes(int n)//线性筛的原理是用最小质因数将这个合数筛掉
{
    for (int i = 2; i <= n; i ++ )
    {
        if (!st[i]) primes[cnt ++ ] = i;//如果遍历到i时，i没被标记说明i为质数，因为在小于i-1的所有数中，没有一个将i筛掉的
        for (int j = 0; primes[j] <= n / i; j ++ )
        {
            st[primes[j] * i] = true;
            //此时primes[j] * i的最小质因子一定是primes[j]，这个结论是由下面的代码维护的
            if (i % primes[j] == 0) break;
            //如果i % primes[j] == 0而不退出的话，下面就是st[primes[j+1] * i] = true，按照惯例，
            //这里的primes[j+1]应该是primes[j+1] * i的最下质因子，但是i的最小质因子为primes[j]
            //primes[j]一定小于primes[j+1]，就不符合最小质因子筛掉所有合数
        }
    }
}

二.约数

1.试除法求单个数的约数

约数一定是成对出现的且范围是2~n/2，成对出现的约数的分割点是sqrt(n)

2.求约数个数：(x1+1)*(x2+1)…(xn+1);

需要唯一分解定理分解这个数，用underored_map存储

3.求约数的和模mod：约数之和： (p1^0+p1^1+p1^2+....+p1^n)..(pn^0+pn^1+pn^2+....+pn^n)

这里用到了一个模板求(p1^1+p1^2+....+p1^n)

for (auto p : primes)
{
    LL a = p.first, b = p.second;
    LL t = 1;
    while (b -- ) t = (t * a + 1) % mod;
    res = res * t % mod;
}

4.最大公约数

三.欧拉函数

1.定义：一个数n的欧拉函数 f(n) = 1~n-1中与n互质数的个数f(n) = n * (pi-1) / pi

2.一个数如果为质数那么它的欧拉函数值为其本身-1

3.筛法求范围内的欧拉函数

用到了线性筛的模板

void get()
{
    for(int i=2;i<=n/i;i++)
    {
        if(!st[i])
        {
            prim[cnt++]=i;
            mum[i]=i-1;
            //如果i为质数，那么它的欧拉值为i-1，因为质数的性质
        }
        for(int j=0;prim[j]<=n/i;j++)
        {
            st[prim[j]*i]=true;
            mum[prim[j]*i]=(prim[j]-1)*mum[i];
            //mum[prim[j]*i]=prim[j]*mum[i]*(1-1/prim[j])
            //prim[j]*i相较于i增加了一个质因数prim[j]（因为prim[j]为质数），
            if(i%prim[j]==0)
            {
                mum[prim[j]*i]=prim[j]*mum[i];
                //如果i%prim[j]==0，prim[j]是i的最小质因子，i*prim[j]它分解质因数以后质因数的值相较于i，不会有增加
                break;
            }
        }
    }
}

四.逆元

逆元的含义：b与p互质，找到一个x，使得 b * x == 1（mod p） ,可以简单地将这个x记作 b^-1。此时除以这个数相当于乘这个数的逆元
根据费马定理：两个互质的数b p，b ^ p - 1 mod p == 1,所以b * b ^ p - 2 mod p == 1,所以b ^ p - 2,就是b的乘法逆元
a模p存在逆元的充分必要条件是gcd(a, p) = 1
p是质数求逆元用快速幂，pi不是质数求逆元的方法是拓展欧几里得算法

五.快速幂

1.快速幂模板

typedef long long LL;
LL qmi(int a, int b, int p)
{
    LL res = 1 % p;//LL res = 1 % p; 当b=0时会发挥作用
    while (b)
    {
        if (b & 1) res = res * a % p;
        a = a * (LL)a % p;
        b >>= 1;
    }
    return res;
}

2.快速幂求逆元(当mod为质数时)

qmi(a,mod-2);

六.拓展欧几里得算法

1.欧几里得算法又称辗转相处法，即gcd

2.拓展欧几里算法

//贝祖等式：对于任意两个整数a和b，存在整数x和y，使得ax + by = gcd(a, b)。这是数论中的一个基本定理，也称为贝祖定理
（1）拓展欧几里得算法存在x，y(不唯一)使得ax * by=gcd(a,b).（2）ax1 * by1=m，若m时gcd的p倍数则x1=px，y1=py
算法核心：当前的x，y的更新依赖于上一层的x，y

设ax1+by1=gcd(a,b), bx2+(a%b)y2=gcd(b,a%b);
由gcd(a,b)=gcd(b,a%b),可得:
ax1+by1=bx2+(a%b)y2;
即:ax1+by1=bx2+(a-(a/b)*b)y2
          =ay2+bx2-(a/b)*by2;
即:ax1+by1=ay2 + b(x2-(a/b)*y2)
根据恒等定理,对应项相等，得:x1=y2; y1=x2-(a/b)*y2;
这样我们就得到了x1，y1的值基于x2，y2，所以我们可以通过递归求解

#include <iostream>
#include <algorithm>

using namespace std;

void exgcd(int a, int b, int &x, int &y)
{
    if (!b)
    {
        x = 1, y = 0;
        return;
    }

    exgcd(b, a % b, y, x);

    y = y - a / b * x;

    //y1=x2-(a/b)*y2;  这里的x2对应y1，即y，y2对应x1，即x，原因：每次递归x，y都会调换
}

3.线性同余方程

a * x == b (mod m) 如果b % gcd(a,b)==0,就存在x使得等式成立
代码如下

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

int main()
{
    int n;
    cin>>n;
    while(n--)
    {
        int a,b,m;
        scanf("%d %d %d",&a,&b,&m);
        int x,y;
        int d=exgcd(a,m,x,y);
        if(b%d==0)
            cout<<(LL)b / d * x % m<<endl;
        //(LL)b / d * x % m这里因为求得结果是a的系数的值，所以将x乘以b / d倍数
        else 
            cout<<"impossible"<<endl;
    }
}

4.拓展欧几里得算法求逆元的原理和方法

（1）推导
由该算法可知ax * by=gcd(a,b)，a模m逆元的转换式为a * x ==（记作同余于）1（mod m）---->a * x + m * y == 1.因为逆元存在的条件是gcd(a,m)=1,所以
a * x + m * y = gcd(a,m) == 1,求出x即可

七.组合数 C(b,a)

1.性质(1).C(b,a)=C(b,a-1)+C(b-1,a-1),(2)lucas定理：C(b,a) mod m = C(b mod m,a mod m) * (b / m,a / m)

2.根据数据范围选择求组合数的方法

(1)1≤n≤10000,1≤b≤a≤2000

void init()
{
    for(int i=1;i<=N;i++)
        for(int j=0;j<=i;j++)
            if(j==0) c[i][j]=0;
            else c[i][j]=(c[i-1][j-1]+c[i-1][j])%mod;
}
时间复杂度为O （N *（n^2））

(2)1≤n≤10000,1≤b≤a≤1e5

f[0] = inf[0] = 1;
for (int i = 1; i < N; i ++ )
{
    f[i] = (LL)f[i - 1] * i % mod;
    inf[i] = (LL)inf[i - 1] * qmi(i, mod - 2, mod) % mod;
}
时间复杂度O（N*n）

(3)
1≤n≤20,1≤b≤a≤1e18,1≤p≤1e5
利用lucas定理

int C(int a, int b, int p)
{
    if (b > a) return 0;

    int res = 1;
    for (int i = 1, j = a; i <= b; i ++, j -- )
    {
        res = (LL)res * j % p;
        res = (LL)res * qmi(i, p - 2, p) % p;
    }
    return res;
}
时间复杂度O(N*p)