逆元,欧拉降幂公式,二次剩余

发布于 2020-07-22  0 次阅读


一.逆元

概念和作用:

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

求法:

1、费马小定律

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

2、扩展欧几里得算法

求 ax ≡ 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 = ki + r ( 0 <= r < i ) ,于是得到ki + 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,式子x2 ≡ 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;
}



平平无奇的大学在读本科生