费马小定理

假如p是质数，且gcd(a,p)=1，那么 $a^{p-1}≡1（mod p）$，即：假如a是整数，p是质数，且a,p互质(即两者只有一个公约数1)，那么a的(p-1)次方除以p的余数恒等于1。

和同余定理可以一起用在当指数很大的时候。比如要整体MOD 1e9+7，可以对指数MOD 1e9+6，然后再将快速幂得到的MOD 1e9+7。参见nbuoj2700。

逆元一般用扩展欧几里得算法来求得，如果为素数，那么还可以根据费马小定理得到逆元为。

逆元

如果ax≡1 (mod p),且gcd(a,p)=1（a与p互质），则称a关于模p的乘法逆元为x。
a和p互质，a才有关于p的逆元。b的逆元，我们用inv(b)来表示，那么(a/b)%p=(a×inv(b))%p=(a%p×inv(b)%p)%p，这样就把除法，完全转换为乘法了 。
逆元的求法：
方法一：用费马小定理。
在p是素数的情况下，x^(p−2)即为x关于p的逆元。

long long PowerMod(int a,int b,int c)
{
    long long ans=1;
    long long k;
    k=a;
    k=k%c;
    while(b>0)
    {
        if(b%2==1)
        ans=(ans*k)%c;
        b=b/2;
        k=(k*k)%c;
    }
    return ans;
}
long long Fermat(int x,int p)
{
    return PowerMod(x,p-2,p);
}

方法二：用扩展欧几里得算法。
因为ax≡1(mod p)，所以ax-py=1，应用一下扩展欧几里得算法即可。

void extgcd(int a,int b,int d,int &x,int &y)   //a,b都为正整数
{
    if(b==0){d=a;x=1;y=0;}
    else{extgcd(b,a%b,d,y,x);y=y-x*(a/b);}
}
int inverse(int a,int p)
{
    int d,x,y;
    extgcd(a,p,d,x,y);
    return d==1?(x%p+p)%p:-1; //x是应为正整数，即需要若x为负整数，则需要将之化正，即与负数取模同理，将x加上p，直至x>0为止，所得的数即为最小的乘法逆元。
}
int main()
{
    int a,p;
    scanf("%d%d",&a,&p);
    inverse(a,p);
    return 0;
}

方法三：线性时间求所有逆元。

void mutl(int mod)
{
	int inv[M];inv[1]=1;//边界条件 
	for (int i=2;i<=M;i++) 
		inv[i]=((-(mod/i)*inv[mod%i])%mod+mod)%mod; //防止出现负数 
	return ; 
}

这个方法不限于求单个逆元，比前两个好，它可以在O(n)的复杂度内算出n个数的逆元，递归就是上面的写法，加一个记忆性递归，就可以了，递推这么写：

int inv[N];
int init(){
    inv[1] = 1;
    for(int i=2;i<N;i++){
        inv[i]=(p-p/i)*inv[p%i]%p;
    }
}

阶乘的逆元

void init()
{
    fac[0]=fac[1]=1;
    for(int i=2;i<=MAXN;i++)
        fac[i]=fac[i-1]*i%MOD;
    inv[MAXN]=PowerMod(fac[MAXN],MOD-2,MOD);
    for(int i=MAXN-1;i>=0;i--)
        inv[i]=inv[i+1]*(i+1)%MOD;
}

调和级数

1+1/2+1/3+……+1/n=ln(n)。

唯一分解定理

任何一个大于1的自然数N，有标准分解式$N=p_1^{a_1}p_2^{a_2}...p_n^{a_n}$。

它的正因子个数为$(1+a_1)(1+a_2)...(1+a_n)$。

正因子数之和为$(1+p_1+p_1^2+...+p_1^{a_1})(1+p_2+p_2^2+...+p_2^{a_2})...(1+p_n+p_n^2+...+p_n^{a_n})$。

费马大定理

当整数n>2时，关于x,y,z的方程$x^n+y^n=z^n$没有正整数解。

勾股数的构造

$a^2+b^2=c^2$，已知a，构造出b和c。

若a=1或a=2，无解；

若a为奇数，$b=\frac{a^2-1}{2}$，$c=\frac{a^2+1}{2}$；

若a为偶数，$b=\frac{a^2}{4}-1$，$c=\frac{a^2}{4}+1$。

过程：

因为$a=b^2-c^2$所以$a=(b+c)*(b-c)$。

当$a^2\%2=1$时，$\left\{\begin{array}{}c+b=a^2 \\c-b=1\end{array}\right.$。

当$a^2\%2=0$时，$\left\{\begin{array}{}c+b=\frac{a^2}{2} \\c-b=2\end{array}\right.$。

解方程即可。