数论简记

模运算

$( a + b ) mod \;p = ( a \;mod \;p + b \;mod \;p ) mod \;p$

$( a * b ) mod \;p = ( (a \;mod \;p) \times (b \;mod \;p) ) mod \;p$

费马小定理

内容：

若$p$为质数，且$gcd(a,b)=1$,那么$a^{p-1} \equiv 1 (mod \; p)$

那么：
$a$在$mod \; p$意义下的乘法逆元就是$a^{p-2}$。

那么如何快速求解幂呢？

两种方法：

分治快速幂

若$b$为偶数，那么

二进制快速幂

扩展欧几里得算法

求解$ax+by=c(a,b,c,x,y \in Z)$,
当且仅当$c=k \cdot gcd(a,b)$

求解$ax+by=gcd(a,b)$

若$b=0$,那么令$x=1$，原方程可化为$a=g$,等式成立

我们知道
$gcd(a,b)=gcd(b,a%b)$

那么我们设$t=\lfloor \frac ab \rfloor$。

$gcd(a,b)=gcd(b,a-tb)$

$gcd(a,b)=by_1+(a-tb)x_1$

$gcd(a,b)=by_1+ax_1-tbx_1$

$gcd(a,b)=ax_1+b(y1-tx1)$

类比：

$ax+by=\gcd(a,b)$

得到：

$x=x_1,y=y_1-tx_1$

求逆元

$t\; \bmod \; p= 1$

$t + x \cdot p = 1$

所以求$ax+by=1$的解。

$\gcd(a,b)=1$

质数

一个数的因子总是成对出现，所以我们判断质数时枚举到$\sqrt{n}$即可。

bool Is_prime(int n);
{
    if(n==1)return false;
    if(n==2||n==3||n==5||n==7)return true;
    for(register int i=2;i*i<=n;i++)
        if(n%i==0)return false;
    return true;    
}

埃氏筛

一个质数的倍数一定不是质数。

#include<cstring>
#include<cmath>
const int MAXN=1000010;
bool prime[MAXN];
void make_prime)()
{
    memset(prime,true,sizeof(prime));
    prime[0]=prime[1]=false;
    int t=sqrt(MAXN);
    for(register int i=2;i<=t;i++)
    {
        if(prime[i])
        {
            for(register int j=2*i;j<MAXN,j+=i)
            {
                prime[j]=false;
            }
        }
    }
    return;
}

欧拉筛

#include<cstring>
#incldue<cmath>
const int MAXN=1000010;
bool prime[MAXN];
int Prime[MAXN];
int num=0;
void make_prime()
{
    memset(prime,true,sizeof(prime));
    prime[0]=prime[1]=false;
    for(int i=2;i<=MAXN;i++)
    {
        if(prime[i])
        {
            Prime[num++]=i;
        }
        for(int j=0;j<num&&i*Prime[j]<MAXN;j++)
        {
            prime[i*Prime[j]]=false;
            if(!(i%Prime[j]))
                break;
        }
    }
    return;
}

用prime[MAXN]标记一个数是不是素数，Prime[MAXN]表示质数有哪些。

如果我们发现prime[i]为真，那么存储质数的Prime[]就要存储进一个新数i。

我的数论模板

inline long long gcd(long long a,long long b){//O(log n)
    return (!b)?a:gcd(b,a%b);
}
inline long long lcm(long long a,long long b){//O(log n)
    return a/gcd(a,b)*b/gcd(a,b);
}
inline long long mod(long long a,long long b,long long p){
    return (a%p+b)%p;
}//O(1)
inline void ex_gcd(int a,int b,int &c,int &x,int &y){
    if(!b)c=a,x=1,y=0;
    else{
        ex_gcd(b,a%b,c,y,x);
        y-=x*(a/b);
    }
}
inline long long quick_power1(long long a,long long b,long long p){
    long long ans=1;
    for(;n;n>>=1,a=a*a%p)if(n&1)res=res*a%p;
    return res;
}//二进制快速幂 O(log n) 
inline long long quick_power2(long long a,long long b,long long p){
    if(n==0)return 1;
    if(n%2==0){
        long long x=quick_power2(a,n/2,p);
        return x*x%p;
    }
    else return a*quick_power2(a,n-1,p);
}//分治快速幂 O(log n) 
inline long long INV_ALL(long long a,long long long p){
    long long GCD,tmp,res;
    ex_gcd(a,p,GCD,res,tmp);
    return mod(res,p,p);
}
inline long long INV_PRIME(long long a,long long p){
    return quick_power1(a,p-2,p);
}
inline void Euler(){
    const int MAXN=1000010;
    bool prime[MAXN];
    int Prime[MAXN],num=0;
    memset(prime,true,sizeof(prime));
    prime[0]=prime[1]=false;
    for(int i=2;i<=MAXN;i++){
        if(prime[i])Prime[num++]=i;
        for(int j=0;j<num&&i*Prime[j]<MAXN;j++){
            prime[i*Prime[j]]=false;
            if(!(i%Prime[j]))break;
        }
    }
    return;
}//欧拉筛 

组合数学

未完。。。