数论（GCD & LCM & 素数 & 快速幂）[挑战程序设计竞赛总结]_stein算法时间复杂度

数论

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

最大公约数GCD

辗转相除法

算法模版

int gcd(int a,int b)
{
  if(a<b) return gcd(b,a);
  if(b==0) return a;
  return gcd(b,a%b);
}
1
2
3
4
5
6

算法时间复杂度

时间复杂度为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);
}
1
2
3
4
5
6

算法时间复杂度

时间复杂度为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);
}
1
2
3
4
5
6
7
8
9
10
11
12
13

算法时间复杂度

时间复杂度为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;
}
1
2
3
4
5
6
7
8
9
10
11
12

算法时间复杂度

时间复杂度为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是个例外
}
1
2
3
4
5
6
7

算法时间复杂度

时间复杂度为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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

算法时间复杂度

时间复杂度为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;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

快速幂

非递归快速幂

算法核心

• 将指数看成二进制位，逐位进行累乘
• 例如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;
}
1
2
3
4
5
6
7
8
9
10
11
12

算法分析

时间复杂度为O(logn)