一.逆元

概念和作用:

逆元其实跟倒数很相似。
逆元概念：方程 a_x≡1(mod p )的解称为 a 关于模 p 的逆，当 gcd(a,p)=1（即 a，p 互质）时，方程有唯一解，否则无解。
逆元的作用：对于求(a/b)mod p，直接除会爆精度，此时就可以采用逆元(a∗inv(b)) mod p.

求法:

1、费马小定律

当 p 为质数时，有 a^p−1≡ 1 (mod p) ,那么易得出 a ∗ a ^{p − 2} ≡ 1 ( m o d    p )
a ^p−2就是 a 关于模 p 的逆元
直接用快速幂即可算出答案，quickpow(b, p−2).

2、扩展欧几里得算法

求 a_x ≡ 1 (mod) p 的一个解，用Exgcd求解即可解决，a、p互质

Code:

void Exgcd(ll a, ll b, ll &x, ll &y) {
    if (!b) x=1,y=0;
    else Exgcd(b,a%b,y,x),y-=a/b*x;
}
int NY(int a,int p){
    ll x,y;
    Exgcd(a,p,x,y);
    return (x%p+p)%p;
}

3、递推

多个连续的乘法逆元，可以采用递推求解
令p = k_i + r ( 0 <= r < i ) ，于是得到k_i + r ≡ 0 ( m o d    p )，等式两边同时乘上i − 1 , r − 1得到kr − 1 + i − 1 ≡ 0 ( m o d    p ) ,移项可得i − 1 ≡ − ⌊ p / i ⌋ ∗ ( p    m o d    i ) − 1 ( m o d    p )
通常写成：
i n v [ i ] = ( ( p − p / i ) ∗ i n v [ p % i ] + p ) % p

Code:

int inv[N];
void get_inverse(int n,int p)
{
	int i;
	inv[1]=1;
	for(i=2;i<=n;++i)
	  inv[i]=(p-p/i)*inv[p%i]%p;

注：

对于Fibonacci Sum题中，求阶乘逆元有两种方法

Code1:

先用递推求得每一位的逆元，再计算阶乘

    finv[1] = 1;
    for( int i = 2; i <=n; i++ )    finv[i] = ( P - P / i ) * finv[ P % i ] % P;
    finv[0]=1; 
    for(int i=1;i<=n;i++)    finv[i]=finv[i]*finv[i-1]%P;

Code2

利用公式1 / ( n + 1 ) ! × ( n + 1 ) = 1 / n ! ，求得1 / n !后倒推回去

    finv[n]=fp(fac[n],P-2);				//这里是用的快速幂和费马小定律算的1/n!的值
    for(int i=n-1;i>=0;i--)		finv[i]=finv[i+1]*(i+1)%P;

二.欧拉降幂公式

a
b
≡
a b % φ ( p )                ( m o d    p ) a^{b\%φ(p)}\, \:\, \:\, \:\, \:\, \:\, \:\, \:(mod\, \: p)a
b%φ(p)
(modp)                    \, \:\, \:\, \:\, \:\, \:\, \:\, \:\, \:\, \: n , a 互 质 n,a互质n,a互质
a b                          ( m o d    p ) a^ b \, \:\, \:\, \:\, \:\, \:\, \:\, \:\, \, \:\, \:\, \:\, \:\:(mod\, \: p)a
b
(modp)                   \, \:\, \:\, \:\, \:\, \:\, \:\, \:\, \:\, \: b < φ ( n ) b<φ(n)b<φ(n)
a b % φ ( n ) + φ ( n )      ( m o d    p ) a ^{b\%φ(n)+φ(n)}\, \:\, \:(mod\, \: p)a
b%φ(n)+φ(n)
(modp)                  \, \:\, \:\, \:\, \:\, \:\, \:\, \:\, \: b ≥ φ ( n ) b≥φ(n)b≥φ(n)

其中φ(n)表示小于等于m的数中与n互质的数的数目
φ(即phi)是欧拉函数

求解欧拉函数代码:

ll euler_phi(ll n) {
    ll k = (ll)sqrt(n + 0.5);
    ll ans = n;
    for(int i = 2; i <= k; i++) {
        if(n % i == 0) {
            ans = ans / i * (i - 1);
            while(n % i == 0)   n /= i;
        }
    }
    if(n > 1)   ans = ans / n * (n - 1);
    return ans;
}

三.二次剩余

概念：

当存在某个X，式子x² ≡ n ( m o d    p )成立时，称“n是模p的二次剩余”
当对任意不成立时，称“ n是模 p的二次非剩余”

作用：

对于一个数n，求根号下n对p取模的时候，可以看n是否是模p的二次剩余，是的话可以用x去代替根号n

Code:

#include<cstdio>
#include<math.h>
#include<algorithm>
using namespace std;
const int mod=1e9 + 9;
typedef long long ll;
template<typename T>
inline int pow(int x,T y)
{
    int res=1;x%=mod;
    for(;y;y>>=1,x=(ll)x*x%mod) if(y&1) res=(ll)res*x%mod;
    return res;
}
inline int Quadratic_residue(const int a)
{
	if(a==0)return 0;
	int b=(rand()<<14^rand())%mod;
	while(pow(b,(mod-1)>>1)!=mod-1)b=(rand()<<14^rand())%mod;
	int s=mod-1,t=0,x,inv=pow(a,mod-2),f=1;
	while(!(s&1))s>>=1,t++,f<<=1;
	t--,x=pow(a,(s+1)>>1),f>>=1;
	while(t)
	{
		f>>=1;
		if(pow((int)((ll)inv*x%mod*x%mod),f)!=1)    x=(ll)x*pow(b,s)%mod;
		t--,s<<=1;
	}
	return min(x,mod-x);
}
int main(){
    int n;
    scanf("%d", &n);
    printf("%d\n", Quadratic_residue(n));
    return 0;
}