数论（OI）

348 字

2 分钟

数论（OI）

2023-09-03

OI

数论

模运算#

$a\%b = a-b*floor(\frac ab)$

费马小定理

$a^{p-1} \% p=1$

最小公倍数&最大公约数#

(a,b)表示最大公约数

[a,b]表示最小公倍数

$(a,b)*[a,b] = ab$

辗转相除

1
if (a % b==0) return b;
2
else return gcd(b, a % b);

质数#

筛法

1
for (int i = 2; i <= n; i++) {
2
    if (is_prime[i])
3
        for (int j = 2*i; j <= n; j+=i) is_prime[j]=false; //筛去当前素数的倍数
4
}

欧拉函数 $\phi$

求互质(公约数只有1的两个整数)个数

快速幂#

在幂指数过大的情况下，快速幂运算

1
int power(int a, int n) {
2
  int tp = 1;
3
  while (n) {
4
    if (n & 1) tp = 1ll * tp * a % mod;
5
    a = 1ll * a * a % mod, n >>= 1;
6
  }
7
  return tp;
8
}

分治#

将 $a^{100}$ 化成 $a^{50}*a^{50}$ ,递归处理

1
#include <bits/stdc++.h>
2
using namespace std;
3

4
typedef long long ll;
5

6
ll a, b, m;
7
int getRes(ll a, ll b, ll m) {
8
  if (b == 0) return 1;
9
  if (b % 2 == 1) {
10
    return a * getRes(a, b - 1, m) % m;
11
  } else {
12
    ll mul = getRes(a, b / 2, m);
13
    return mul * mul % m;
14
  }
15
}
16

17
int main() {
18
  cin >> a >> b >> m;
19
  cout << getRes(a, b, m);
20
  return 0;
21
}

迭代#

将幂指数作二进制数位运算

1
#include <bits/stdc++.h>
2
using namespace std;
3
typedef long long ll;
4

5
ll a, b, m;
6

7
int main() {
8
  cin >> a >> b >> m;
9
  ll ans = 1, cur = a;
10
  while (b > 0) {
11
    if (b & 1) ans = ans * cur % m;
12
    cur = cur * cur % m;
13
    b >>= 1;
14
  }
15
  cout << ans;
16
  return 0;
17
}

数论（OI）

https://c0d4.ink/posts/数论/

作者

Coda

发布于

2023-09-03

许可协议

CC BY-NC-SA 4.0

对拍

链表