数论

Posted on In

数论

常用的一些小小数论知识

模运算

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

费马小定理

ap−1%p=1a^{p-1} \% p=1

最小公倍数&最大公约数

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

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

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

辗转相除

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


质数

筛法

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

欧拉函数 ϕ\phi

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



快速幂

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

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

分治

将a100a^{100}化成a50∗a50a^{50}*a^{50},递归处理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

ll a, b, m;
int getRes(ll a, ll b, ll m) {
	if (b == 0) return 1;
	if (b % 2 == 1) {
		return a * getRes(a, b - 1, m) % m;
	} else {
		ll mul = getRes(a, b / 2, m);
		return mul * mul % m;
	}
}

int main() {
	cin >> a >> b >> m;
	cout << getRes(a, b, m); 
	return 0;
}

迭代

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll a, b, m;

int main() {
	cin >> a >> b >> m;
	ll ans = 1, cur = a;
	while (b > 0) {
		if (b & 1) ans = ans * cur % m;
		cur = cur * cur % m;
		b >>= 1;
	}
	cout << ans;
	return 0;
}