求逆元模板-费马小定理&&拓展欧几里得&&线性递推

向右看齐 2022-10-11 14:53 161阅读 0赞

前两个定理求单个逆元可以，如果求多个，用线性递推。  
发现cin cout 实在是太慢了，还是老实使用scanf printf

**费马小定理：**

**a ( p − 1 ) ≡ 1 ( m o d   p ) a^\{(p-1) \}≡ 1 (mod \\ p) a(p−1)≡1(mod p)** 两边同时除以a 得：

a ( p − 2 ) ≡ i n v ( a ) ( m o d   p ) a^\{(p-2) \}≡ inv(a) (mod \\ p) a(p−2)≡inv(a)(mod p)

i n v ( a ) = a ( p − 2 ) ( m o d   p ) inv(a) = a^\{(p-2) \} (mod \\ p) inv(a)=a(p−2)(mod p)

int m_pow(int a, int b, const int p){ 
        int c = 1;
        for(;b;b>>=1,a=1LL*a*a%p)
            if(b&1) c=1LL*c*a%p;
        return c;
    }
    
    int inv(int a, int p){ 
        return m_pow(a, p-2, p);
    }

**拓展欧几里得定理：**

a \* inv(a) = 1 (mod p)

a \* inv(a) + p\*t = 1 (mod p)

a \* x + py = 1  
(x= inv(a) , y = t)

int x,y;
    void exgcd(int a,int b){ 
      if(!b){ x=1,y=0;return ;}
      exgcd(b,a%b);
      int t=x;
      x=y,y=t-a/b*y;
    }
    void inv(int a, int p) // p 是 mod
    { 
    	exgcd(a,p);
    	return (x%p+p)%p;
    }

另外一种写法，为了防止无解情况，判断一下。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1a2VyNg_size_16_color_FFFFFF_t_70]

void exgcd(int a, int &x0, int b, int &y0, int &d)
    { 
    	if(b==0)
    	{ 
    		x0 = 1;
    		y0 = 0;
    		d = a;
    		return;	
    	}
    	int x1, y1;
    	exgcd(b, x1, a%b, y1, d);
    	x0 = y1;
    	y0 = x1 - (a/b)*y1;
    }
    void inv(int a, int p)
    { 
    	int x, y, d;
    	exgcd(a,x,b,y,d);
    	if(d!=1) return -1;
    	return (x%p+p)%p;
    }

**线性递推：**

p = k ∗ i + r , k = ⌊ p i ⌋   k ∗ i + r ≡ 0 ( m o d   p )   同 时 乘 以 i − 1 ∗ r − 1   k ∗ r − 1 + i − 1 ≡ 0 ( m o d   p )   i − 1 ≡ − k ∗ r − 1 ( m o d   p )   i − 1 ≡ − ⌊ p i ⌋ ∗ ( p   m o d   i ) − 1 ( m o d   p ) p = k\*i+ r , k = \\lfloor \\frac\{p\}\{i\} \\rfloor \\\\ \\ \\\\ k\*i + r \\equiv 0 (mod \\ p) \\\\ \\ \\\\ 同时乘以 i^\{-1\}\*r^\{-1\} \\\\ \\ \\\\ k\*r^\{-1\} + i^\{-1\} \\equiv 0 (mod \\ p) \\\\ \\ \\\\ i^\{-1\} \\equiv -k\*r^\{-1\}(mod \\ p) \\\\ \\ \\\\i^\{-1\} \\equiv -\\lfloor \\frac\{p\}\{i\} \\rfloor \* (p \\ mod \\ i )^\{-1\}(mod \\ p) p=k∗i\+r,k=⌊ip⌋ k∗i\+r≡0(mod p) 同时乘以i−1∗r−1 k∗r−1\+i−1≡0(mod p) i−1≡−k∗r−1(mod p) i−1≡−⌊ip⌋∗(p mod i)−1(mod p)  
右边式子加上p没有影响；

void seive_inv(const int a, const int p) // p就是mod
    { 
    	inv[0] = inv[1] = 1; // 规定一下
    	rep(i,2,n) inv[i] = 1LL*(p-p/i)*inv[p%i]%p;
    }

注：模板是就“借”来的

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1a2VyNg_size_16_color_FFFFFF_t_70]: /images/20221005/7e801f65f47c4277b4931e3569fb6258.png