banner
NEWS LETTER

基础数论 | OI笔记

Scroll down

最大公约数(gcd)

使用辗转相除法求解

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

或简化写法

c++
1
2
3
4
5
int gcd(int a, int b)
{
return b ? gcd(b, a % b) : a;
//or return b == 0 ? a : gcd(b, a % b);
}

最小公倍数(lcm)

原理

  • 最小公倍数可理解为去除两个数一个公共因数之后的乘积
  • 最大公因数可理解为两个数公共因数的乘积
  • 这样就容易得到两者乘积为这两个数的乘积

gcd(a,b)lcm(a,b)=ab\text{gcd}(a, b) * \text{lcm}(a, b) = a * b

  • 由此即可得到
    lcm(a,b)=abgcd(a,b)\text{lcm}(a, b) = \frac{a * b}{\text{gcd}(a, b)}

代码实现

c++
1
2
3
4
5
6
7
8
9
int gcd(int a, int b)
{
return b ? gcd(b, a % b) : a;
}

int lcm(int a, int b)
{
return a * b / gcd(a, b);
}

素数

线性筛

c++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int primes[N], cnt; //primes存储所有素数
bool st[N]; //st[x]存储x是否被筛掉

void get_primes(int n)
{
for(int i = 2; i <= n; i ++)
{
if(!st[i])
primes[cnt ++] = i;
for(int j = 0; primes[j] <= n / i; j ++)
{
st[primes[j] * i] = true;
if(i % primes[j] == 0)
break;
}
}
}

快速幂

mk(modp)m ^ k \pmod p,时间复杂度为O(logk)O(\log{k})

c++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
int qpow(int m, int k, int p)
{
int res = 1 % p, t = m;

while(k)
{
if(k & 1)
res = res * t % p;
t = t * t % p;
k >>= 1;
}

return res;
}
Other Articles
Nickname
Email
Website
0/500
0 comments
Please enter keywords to search