数论（GCD & LCM & 素数 & 快速幂）[挑战程序设计竞赛总结]

布满荆棘的人生 2023-07-05 11:51 19阅读 0赞

# 数论 #

数论算法：最大公约数、最小公倍数、素数、快速幂

# 最大公约数GCD #

## 辗转相除法 ##

### 算法模版 ###

int gcd(int a,int b)
    {
        
      if(a<b) return gcd(b,a);
      if(b==0) return a;
      return gcd(b,a%b);
    }

### 算法时间复杂度 ###

时间复杂度为`O(logmax(a,b))`

## 更相减损法 ##

### 算法模版 ###

int gcd(int a,int b)
    {
        
      if(a<b) return gcd(b,a);
      if(b==0) return a;
      return gcd(b,a-b);
    }

### 算法时间复杂度 ###

时间复杂度为`O(max(a,b))`

## stein算法（更相减损+移位运算） ##

### 算法模版 ###

int gcd(int a,int b)
    {
        
      if(a==b) return a;
      if(a<b) return gcd(b,a);
      if(!a&1 && !b&1)
        return 2*gcd(a>>1,b>>1);
      else if(!a&1 && b&1)
        return gcd(a>>1,b);
      else if(a&1 && !b&1)
        return gcd(a,b>>1);
      else
        return gcd(b,a-b);
    }

### 算法时间复杂度 ###

时间复杂度为`O(logmax(a,b))`，但相比辗转相除法更加稳定

## 扩展欧几里德 ##

> 存在两个整数`a,b`,并且`gcd(a,b)=c`,那么一定存在两个数`x,y`，使得`**a*x+b\*y=c**`

### 可用于求逆元 ###

> 当c=1时，x即为a的逆元

### 逆元算法推导（部分） ###

\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-GOyp8pOZ-1581681221152)(/assets/blogImg/gcd-primenumber-quickmi/ex-gcd1.JPG)\]

### 算法模版 ###

int ex_gcd(int a,int b,int &x,int &y)
    {
        
      int d=a;
      if(b!=0){
        
        d=ex_gcd(b,a%b,y,x);
        y-=(a/b)*x;
      }
      else{
        
        x=1;y=0;
      }
      return d;
    }

### 算法时间复杂度 ###

时间复杂度为`O(logmax(a,b))`

# 最小公倍数LCM #

> 若存在两个整数`x,y`,使得`GCD(x,y)=m`,那么`LCM=x*y/m`

# 素数 #

## 素数判定 ##

### 算法模版 ###

bool is_prime(int n)
    {
        
      for(int i=2;i*i<n;i++){
        
        if(n%i==0)  return false;
      }
      return n!=1;  //n是个例外
    }

### 算法时间复杂度 ###

时间复杂度为`O(n^1/2)`

## 埃氏筛法 ##

### 算法核心 ###

> 如果最小的数字2是素数，那么将表中所有2的倍数都划去  
> 如果最小的数字3是素数，那么将表中所有3的倍数都划去  
> 如果表中剩余的数字m是素数，那么将表中所有m的倍数都划去

### 算法模版 ###

const int MAX_N=100000;
    int prime[MAX_N]; //记录从2～n的所有素数，即第i个素数
    bool is_prime[MAX_N+1]; //is_prime[i]=true 表示i是素数
    
    //返回n以内素数的个数
    int sieve(int n)
    {
        
      int count=0;
    
      for(int i=0;i<=n;i++) is_prime[i]=true; //初始化
    
      is_prime[0]=is_prime[1]=false;
    
      for(int i=2;i<=n;i++){
        
        if(is_prime[i]){
        
          prime[count++]=i;
          for(int j=2*i;j<=n;j+=i)  is_prime[j]=false;
        }
      }
      return count;
    }

### 算法时间复杂度 ###

时间复杂度为`O(nloglogn)`

## 区间素数 ##

例如区间`[a,b)`内的素数

### 算法核心 ###

> 通过对区间\[2,b^1/2)的素数来对\[a,b)区间内进行埃氏筛选

### 算法模版 ###

const int MAX_B=100000;
    int is_prime[MAX_B];
    
    int segment_sieve(int a,int b)
    {
        
      int count=0;
    		for(int i=2;i*i<=b;i++){
        
    			if(!is_prime[i]){
        
    				for(int j=2*i;j<=b;j+=i)
    					is_prime[j]=1;
    				count ++;
    			}
    		}
      return count;
    }

# 快速幂 #

## 非递归快速幂 ##

### 算法核心 ###

*  将指数看成二进制位，逐位进行累乘
 *  例如`x^22`可看成`x^16*x^4\*x^2`

### 算法模版 ###

typedef long long ll;
    
    ll mod_pow(ll x, ll n, ll mod)
    {
        
      ll res = 1;
      while(n > 0){
        
        if(n & 1) res = res * x % mod;  //如果二进制最低位为1，则乘上x^(2^i)
        x = x * x % mod;  //将x平方
        n >>= 1;
      }
      return res;
    }

### 算法分析 ###

时间复杂度为`O(logn)`