C++编程提升之路第二课——数学

众所周知，数学在我们编程当中是非常重要的。一些题目，你用纯暴力肯定会超时，而经过数学优化后复杂度就会降低很多。

• 其实这个算法就是 g c d ( a , b ) = g c d ( b , a   m o d   b ) gcd(a,b)=gcd(b,a~mod~b) gcd(a,b)=gcd(b,a mod b) 但是要证明它并不是很容易。

• 我们可以先证明： g c d ( a , b ) = g c d ( b , a − b ) gcd(a,b)=gcd(b,a-b) gcd(a,b)=gcd(b,a−b)

  • 我们设 d = g c d ( a , b ) d=gcd(a,b) d=gcd(a,b) ,则 a = d ⋅ a 1 a=dcdot a1 a=d⋅a1 , b = d ⋅ b 1 b=dcdot b1 b=d⋅b1 且 g c d ( a 1 , b 1 ) = 1 gcd(a1,b1)=1 gcd(a1,b1)=1

  • 且 a − b = d ⋅ e s a 1 − d ⋅ b 1 = d ⋅ ( a 1 − b 1 ) a-b=d cdot es a1-d cdot b1=d cdot (a1-b1) a−b=d⋅esa1−d⋅b1=d⋅(a1−b1)

  • 那么 a − b a-b a−b 和 b b b 都有一个公因子 d d d，接下来只需证明：

  • g c d ( b 1 , a 1 − b 1 ) = 1 gcd(b1,a1-b1)=1 gcd(b1,a1−b1)=1

  • 我们采用反证法

  • 设 b 1 = β ⋅ λ b1=beta cdot lambda b1=β⋅λ, a 1 − b 1 = α ⋅ λ ( λ > 1 ) a1-b1=alpha cdot lambda(lambda>1) a1−b1=α⋅λ(λ>1)

  • 则 a 1 = a 1 − b 1 + b 1 = λ ⋅ ( α + β ) a1=a1-b1+b1=lambda cdot (alpha + beta) a1=a1−b1+b1=λ⋅(α+β)

  • 因为之前我们已经定义 g c d ( a 1 , b 1 ) = 1 gcd(a1,b1)=1 gcd(a1,b1)=1且 b 1 = λ ⋅ β b1=lambda cdot beta b1=λ⋅β

  • 那么 λ lambda λ只能等于1

  • 与命题不符，得证

• ∵ g c d ( a , b ) = g c d ( b , a − b ) because gcd(a,b)=gcd(b,a-b) ∵gcd(a,b)=gcd(b,a−b)

• ∴ g c d ( a , b ) = g c d ( b , a − b ) = g c d ( b , a − 2 b ) = g c d ( b , a − 3 b ) . . . therefore gcd(a,b)=gcd(b,a-b)=gcd(b,a-2b)=gcd(b,a-3b)... ∴gcd(a,b)=gcd(b,a−b)=gcd(b,a−2b)=gcd(b,a−3b)...

• ∴ g c d ( a , b ) = g c d ( b , a   m o d   b ) therefore gcd(a,b)=gcd(b,a~mod~b) ∴gcd(a,b)=gcd(b,a mod b)

• 得证！

• 根据此定理，我们可以快速求出两个数的 g c d gcd gcd 。

• 代码：

#include
using namespace std;
inline int gcd(int n,int m){
	if(b==0)return a;
	return gcd(b,a%b);
}
int main(){
	int n,m;
	cin>>n>>m;
	cout< 
三：扩展欧几里得算法 
1:介绍 
它就是求 
     
      
       
        
         a
        
        
         x
        
        
         +
        
        
         b
        
        
         y
        
        
         =
        
        
         g
        
        
         c
        
        
         d
        
        
         (
        
        
         a
        
        
         ,
        
        
         b
        
        
         )
        
       
       
        ax+by=gcd(a,b)
       
      
     ax+by=gcd(a,b) 
  
显然，当 
       
        
         
          
           b
          
          
           =
          
          
           0
          
         
         
          b=0
         
        
       b=0 时，则原方程变为 
       
        
         
          
           a
          
          
           x
          
          
           =
          
          
           a
          
         
         
          ax=a
         
        
       ax=a,解为
       
        
         
          
           {
          
          
           
            
             
              
               
                x
               
               
                =
               
               
                1
               
              
             
            
           
           
            
             
              
               
                y
               
               
                =
               
               
                0
               
              
             
            
           
          
         
         
          begin{cases} x=1\ y=0\ end{cases}
         
        
       {x=1y=0​
若 
       
        
         
          
           b
          
          
           ≠
          
          
           0
          
         
         
          bne0
         
        
       b​=0，且有 
       
        
         
          
           
            x
           
           
            1
           
          
          
           ,
          
          
           
            y
           
           
            1
           
          
         
         
          x_1,y_1
         
        
       x1​,y1​满足
       
        
         
          
           a
          
          
            
          
          
           m
          
          
           o
          
          
           d
          
          
            
          
          
           b
          
          
           ⋅
          
          
           
            x
           
           
            1
           
          
          
           +
          
          
           b
          
          
           ⋅
          
          
           y
          
          
           1
          
          
           =
          
          
           g
          
          
           c
          
          
           d
          
          
           (
          
          
           b
          
          
           ,
          
          
           a
          
          
            
          
          
           m
          
          
           o
          
          
           d
          
          
            
          
          
           b
          
          
           )
          
         
         
          a~mod~b cdot x_1+b cdot y1=gcd(b,a~mod~b)
         
        
       a mod b⋅x1​+b⋅y1=gcd(b,a mod b)，则有解 
       
        
         
          
           {
          
          
           
            
             
              
               
                x
               
               
                =
               
               
                
                 x
                
                
                 1
                
               
              
             
            
           
           
            
             
              
               
                y
               
               
                =
               
               
                
                 y
                
                
                 1
                
               
               
                −
               
               
                
                 x
                
                
                 1
                
               
               
                ⋅
               
               
                f
               
               
                l
               
               
                o
               
               
                o
               
               
                r
               
               
                (
               
               
                a
               
               
                /
               
               
                b
               
               
                )
               
              
             
            
           
          
         
         
          begin{cases} x=x_1\y=y_1-x_1 cdot floor(a/b)\end{cases}
         
        
       {x=x1​y=y1​−x1​⋅floor(a/b)​
下面为证明过程 
    

         
          
           
            
             ∵
            
            
             (
            
            
             a
            
            
              
            
            
             m
            
            
             o
            
            
             d
            
            
              
            
            
             b
            
            
             )
            
            
             ⋅
            
            
             
              x
             
             
              1
             
            
            
             +
            
            
             b
            
            
             ⋅
            
            
             
              y
             
             
              1
             
            
            
             =
            
            
             g
            
            
             c
            
            
             d
            
            
             (
            
            
             b
            
            
             ,
            
            
             a
            
            
              
            
            
             m
            
            
             o
            
            
             d
            
            
              
            
            
             b
            
            
             )
            
           
           
            because(a~mod~b)cdot x_1+b cdot y_1=gcd(b,a~mod~b)
           
          
         ∵(a mod b)⋅x1​+b⋅y1​=gcd(b,a mod b)

         
          
           
            
             ∴
            
            
             (
            
            
             a
            
            
             −
            
            
             f
            
            
             l
            
            
             o
            
            
             o
            
            
             r
            
            
             (
            
            
             a
            
            
             /
            
            
             b
            
            
             )
            
            
             ⋅
            
            
             b
            
            
             )
            
            
             ⋅
            
            
             
              x
             
             
              1
             
            
            
             +
            
            
             b
            
            
             ⋅
            
            
             
              y
             
             
              1
             
            
            
             =
            
            
             g
            
            
             c
            
            
             d
            
            
             (
            
            
             a
            
            
             ,
            
            
             b
            
            
             )
            
           
           
            therefore(a-floor(a/b)cdot b) cdot x_1+bcdot y_1=gcd(a,b)
           
          
         ∴(a−floor(a/b)⋅b)⋅x1​+b⋅y1​=gcd(a,b)

         
          
           
            
             ∴
            
            
             a
            
            
             ⋅
            
            
             
              x
             
             
              1
             
            
            
             +
            
            
             b
            
            
             ⋅
            
            
             (
            
            
             
              y
             
             
              1
             
            
            
             −
            
            
             
              x
             
             
              1
             
            
            
             ⋅
            
            
             (
            
            
             f
            
            
             l
            
            
             o
            
            
             o
            
            
             r
            
            
             (
            
            
             a
            
            
             /
            
            
             b
            
            
             )
            
            
             )
            
            
             =
            
            
             g
            
            
             c
            
            
             d
            
            
             (
            
            
             a
            
            
             ,
            
            
             b
            
            
             )
            
           
           
            therefore acdot x_1+bcdot (y_1-x_1cdot (floor(a/b))=gcd(a,b)
           
          
         ∴a⋅x1​+b⋅(y1​−x1​⋅(floor(a/b))=gcd(a,b)
证毕
 
根据此结论，我们可以一直递归，直至 
       
        
         
          
           b
          
          
           =
          
          
           0
          
         
         
          b=0
         
        
       b=0
 
 
2：code 
代码：
 
#include
using namespace std;
void ex_gcd(int a,int b,int &x,int &y){//求a*x+b*y=gcd(a,b)的整数解 
	if(!b){
		x=1;
		y=0;
		return;
	}
	ex_gcd(b,a%b,y,x);
	y-=(a/b)*x;
}
int main(){
	int a,b,x,y;
	cin>>a>>b;
	ex_gcd(a,b,x,y);
	cout< 
3：拓展1 
题目：解方程 
     
      
       
        
         a
        
        
         x
        
        
         +
        
        
         b
        
        
         y
        
        
         =
        
        
         c
        
       
       
        ax+by=c
       
      
     ax+by=c 
  
思路：我们设 
       
        
         
          
           d
          
          
           =
          
          
           g
          
          
           c
          
          
           d
          
          
           (
          
          
           a
          
          
           ,
          
          
           b
          
          
           )
          
         
         
          d=gcd(a,b)
         
        
       d=gcd(a,b) ,再把等式两边同时乘上
       
        
         
          
           
            d
           
           
            c
           
          
         
         
          frac{d}{c}
         
        
       cd​
则原方程化为
       
        
         
          
           a
          
          
           ⋅
          
          
           
            d
           
           
            c
           
          
          
           ⋅
          
          
           x
          
          
           +
          
          
           b
          
          
           ⋅
          
          
           
            d
           
           
            c
           
          
          
           ⋅
          
          
           y
          
          
           =
          
          
           g
          
          
           c
          
          
           d
          
          
           (
          
          
           a
          
          
           ,
          
          
           b
          
          
           )
          
         
         
          acdot frac{d}{c} cdot x+bcdotfrac{d}{c}cdot y=gcd(a,b)
         
        
       a⋅cd​⋅x+b⋅cd​⋅y=gcd(a,b)
求解一个
       
        
         
          
           a
          
          
           ⋅
          
          
           
            x
           
           
            ′
           
          
          
           +
          
          
           b
          
          
           ⋅
          
          
           
            y
           
           
            ′
           
          
          
           =
          
          
           g
          
          
           c
          
          
           d
          
          
           (
          
          
           a
          
          
           ,
          
          
           b
          
          
           )
          
         
         
          acdot x'+bcdot y'=gcd(a,b)
         
        
       a⋅x′+b⋅y′=gcd(a,b)
则方程的解为
       
        
         
          
           {
          
          
           
            
             
              
               
                x
               
               
                =
               
               
                
                 x
                
                
                 ′
                
               
               
                ⋅
               
               
                
                 d
                
                
                 c
                
               
              
             
            
           
           
            
             
              
               
                y
               
               
                =
               
               
                
                 y
                
                
                 ′
                
               
               
                ⋅
               
               
                
                 d
                
                
                 c
                
               
              
             
            
           
          
         
         
          begin{cases} x=x'cdotfrac{d}{c}\ y=y'cdotfrac{d}{c}\ end{cases}
         
        
       {x=x′⋅cd​y=y′⋅cd​​
若
        
         
          
           
            c
           
           
            ∤
           
           
            d
           
          
          
           cnmid d
          
         
        c∤d,则原方程无解
 
 
4：拓展2 
题目：解方程 
     
      
       
        
         a
        
        
         ⋅
        
        
         x
        
        
         ≡
        
        
         b
        
        
        
        
         (
        
        
         
          m
         
         
          o
         
         
          d
         
        
        
        
         p
        
        
         )
        
       
       
        a cdot x equiv b pmod p
       
      
     a⋅x≡b(modp) 
  
思路：此题非常简单，将它化为拓展1
原方程化为 
       
        
         
          
           a
          
          
           x
          
          
           +
          
          
           p
          
          
           y
          
          
           =
          
          
           b
          
         
         
          ax+py=b
         
        
       ax+py=b 再用拓展1解即可
若 
        
         
          
           
            b
           
           
            =
           
           
            1
           
          
          
           b=1
          
         
        b=1 ,则此题化为了求解 
        
         
          
           
            a
           
          
          
           a
          
         
        a 在 
        
         
          
           
            m
           
           
            o
           
           
            d
           
           
             
           
           
            p
           
          
          
           mod~p
          
         
        mod p 意义下的逆元。
 
 
四：逆元的求法 
逆元的定义为若 
     
      
       
        
         a
        
        
         ⋅
        
        
         x
        
        
         ≡
        
        
         b
        
        
        
        
         (
        
        
         
          m
         
         
          o
         
         
          d
         
        
        
        
         p
        
        
         )
        
       
       
        a cdot x equiv b pmod p
       
      
     a⋅x≡b(modp)
求解方式有一下几种：
 
1：费马小定理（p为质数） 
费马小定理：
     
      
       
        
         
          a
         
         
          
           p
          
          
           −
          
          
           1
          
         
        
        
         ≡
        
        
         1
        
        
        
        
         (
        
        
         
          m
         
         
          o
         
         
          d
         
        
        
        
         p
        
        
         )
        
       
       
        a^{p-1} equiv 1 pmod p
       
      
     ap−1≡1(modp),证明此处省略
则
     
      
       
        
         a
        
        
         ⋅
        
        
         
          a
         
         
          
           p
          
          
           −
          
          
           2
          
         
        
        
         ≡
        
        
         1
        
        
        
        
         (
        
        
         
          m
         
         
          o
         
         
          d
         
        
        
        
         p
        
        
         )
        
       
       
        acdot a^{p-2} equiv 1 pmod p
       
      
     a⋅ap−2≡1(modp)

     
      
       
        
         ∴
        
        
         a
        
       
       
        therefore a
       
      
     ∴a在
     
      
       
        
         m
        
        
         o
        
        
         d
        
        
          
        
        
         p
        
       
       
        mod~p
       
      
     mod p意义下的逆元为
     
      
       
        
         
          a
         
         
          
           p
          
          
           −
          
          
           2
          
         
        
       
       
        a^{p-2}
       
      
     ap−2
只需使用一个快速幂就好了
代码：
 
#include
using namespace std;
int power(int a,int b,int p){
	int ans=1;
	while(b){
		if(b&1)ans=ans*a%p;
		a=a*a%p;b>>=1;
	}
	return ans;
}
int inv(int x,int p){
	return power(x,p-2,p);
}
int main(){
	int x,p;
	cin>>x>>p;
	cout< 
2：线性求逆元（p为质数） 
当我们要求 
     
      
       
        
         1
        
       
       
        1
       
      
     1到
     
      
       
        
         n
        
       
       
        n
       
      
     n 中所有的数的逆元
我们用一个 
     
      
       
        
         i
        
        
         n
        
        
         v
        
        
         [
        
        
         i
        
        
         ]
        
       
       
        inv[i]
       
      
     inv[i] 来存 
     
      
       
        
         i
        
       
       
        i
       
      
     i 的逆元
设我们要求的是 
     
      
       
        
         i
        
        
         n
        
        
         v
        
        
         [
        
        
         i
        
        
         ]
        
       
       
        inv[i]
       
      
     inv[i] ,且 
     
      
       
        
         p
        
        
         =
        
        
         k
        
        
         ⋅
        
        
         i
        
        
         +
        
        
         r
        
        
         (
        
        
         r
        
        
         <
        
        
         i
        
        
         )
        
       
       
        p=kcdot i+r(r
又因为 
     
      
       
        
         p
        
       
       
        p
       
      
     p 为质数，则 
     
      
       
        
         0
        
        
         <
        
        
         r
        
        
         <
        
        
         i
        
       
       
        0
且 
     
      
       
        
         k
        
        
         =
        
        
         ⌊
        
        
         x
        
        
         ⌋
        
        
         ,
        
        
         r
        
        
         =
        
        
         p
        
        
          
        
        
         m
        
        
         o
        
        
         d
        
        
          
        
        
         i
        
        
         ,
        
        
         k
        
        
         ×
        
        
         i
        
        
         +
        
        
         r
        
        
         ≡
        
        
         0
        
        
        
        
         (
        
        
         
          m
         
         
          o
         
         
          d
         
        
        
        
         p
        
        
         )
        
       
       
        k=lfloor x rfloor,r=p~mod~i,ktimes i+r equiv 0pmod p
       
      
     k=⌊x⌋,r=p mod i,k×i+r≡0(modp)
将等式两边同时乘以 
     
      
       
        
         i
        
        
         ,
        
        
         r
        
       
       
        i,r
       
      
     i,r 的逆元

     
      
       
        
         k
        
        
         ⋅
        
        
         i
        
        
         n
        
        
         v
        
        
         [
        
        
         r
        
        
         ]
        
        
         +
        
        
         i
        
        
         n
        
        
         v
        
        
         [
        
        
         i
        
        
         ]
        
        
         ≡
        
        
         0
        
        
        
        
         (
        
        
         
          m
         
         
          o
         
         
          d
         
        
        
        
         p
        
        
         )
        
        
         ⇒
        
        
         i
        
        
         n
        
        
         v
        
        
         [
        
        
         i
        
        
         ]
        
        
         ≡
        
        
         −
        
        
         k
        
        
         ⋅
        
        
         i
        
        
         n
        
        
         v
        
        
         [
        
        
         r
        
        
         ]
        
        
        
        
         (
        
        
         
          m
         
         
          o
         
         
          d
         
        
        
        
         p
        
        
         )
        
        
         d
        
        
         ⇒
        
        
         i
        
        
         n
        
        
         v
        
        
         [
        
        
         i
        
        
         ]
        
        
         ≡
        
        
         ⌊
        
        
         
          p
         
         
          i
         
        
        
         ⌋
        
        
         ⋅
        
        
         i
        
        
         n
        
        
         v
        
        
         [
        
        
         p
        
        
          
        
        
         m
        
        
         o
        
        
         d
        
        
          
        
        
         i
        
        
         ]
        
        
        
        
         (
        
        
         
          m
         
         
          o
         
         
          d
         
        
        
        
         p
        
        
         )
        
       
       
        kcdot inv[r]+inv[i] equiv 0pmod pRightarrow inv[i]equiv -kcdot inv[r] pmod pdRightarrow inv[i]equiv lfloor frac{p}{i} rfloor cdot inv[p~ mod~i] pmod p
       
      
     k⋅inv[r]+inv[i]≡0(modp)⇒inv[i]≡−k⋅inv[r](modp)d⇒inv[i]≡⌊ip​⌋⋅inv[p mod i](modp)

      
       
        
         
          ∴
         
         
          i
         
         
          n
         
         
          v
         
         
          [
         
         
          i
         
         
          ]
         
         
          =
         
         
          (
         
         
          p
         
         
          −
         
         
          ⌊
         
         
          
           p
          
          
           i
          
         
         
          ⌋
         
         
          ⋅
         
         
          i
         
         
          n
         
         
          v
         
         
          [
         
         
          p
         
         
           
         
         
          m
         
         
          o
         
         
          d
         
         
           
         
         
          i
         
         
          ]
         
         
          )
         
        
        
         therefore inv[i]=(p- lfloor frac{p}{i} rfloor cdot inv[p~ mod~i] )
        
       
      ∴inv[i]=(p−⌊ip​⌋⋅inv[p mod i])
根据此递推式，即可写出代码
 
#include
using namespace std;
const int N=3e6+7;
int n,p;
long long inv[N];
int main(){
	cin>>n>>p;
	inv[1]=1;
	for(int i=2;i<=n;i++)
	inv[i]=(p-p/i)*inv[p%i]%p;
	for(int i=1;i<=n;i++){
		cout< 
3:扩展欧几里得求逆元 
根据我们之前学的扩展欧几里得拓展2的例题：
求
     
      
       
        
         a
        
        
         ⋅
        
        
         x
        
        
         ≡
        
        
         b
        
        
        
        
         (
        
        
         
          m
         
         
          o
         
         
          d
         
        
        
        
         p
        
        
         )
        
       
       
        a cdot x equiv b pmod p
       
      
     a⋅x≡b(modp)
将b换为1即可
 
#include
using namespace std;
void ex_gcd(int a,int b,int &x,int &y){//求a*x+b*y=gcd(a,b)的整数解 
	if(!b){
		x=1;
		y=0;
		return;
	}
	ex_gcd(b,a%b,y,x);
	y-=(a/b)*x;
}
int get_inv(int a,int p){
	int x,y;
	ex_gcd(a,p,x,y);
	x=(x%p+p)%p;//求最小的逆元
	return x; 
} 
int main(){
	int a,p;
	cin>>a>>p;
	cout< 
5:结语 
想必通过今天作者对大家的总结，大家的数学水平都应该有一定的提升了吧，写code的能力估计也强了好几倍，希望在这段时间了，我们一起努力，一起进步！有什么错误还请各位大佬指出。