本文作者：Zhang, Xuheng
本文分类：编程学习笔记 浏览：1625
阅读时间：2970字, 约3.5-5分钟
注意标题：简单。
素数
素性测试
- Fermat 小定理乱搞
bool millerRabin(int n) {
if (n < 3) return n == 2;
// test_time 为测试次数,建议设为不小于 8
// 的整数以保证正确率,但也不宜过大,否则会影响效率
for (int i = 1; i <= test_time; ++i) {
int a = rand() % (n - 2) + 2;
if (quickPow(a, n - 1, n) != 1) return 0;
}
return 1;
}
显然有出错概率。
比较正确的：
bool millerRabbin(int n) {
if (n < 3) return n == 2;
int a = n - 1, b = 0;
while (a % 2 == 0) a /= 2, ++b;
// test_time 为测试次数,建议设为不小于 8
// 的整数以保证正确率,但也不宜过大,否则会影响效率
for (int i = 1, j; i <= test_time; ++i) {
int x = rand() % (n - 2) + 2, v = quickPow(x, a, n);
if (v == 1 || v == n - 1) continue;
for (j = 0; j < b; ++j) {
v = (long long)v * v % n;
if (v == n - 1) break;
}
if (j >= b) return 0;
}
return 1;
}
求因子数一定的最小数。
#include <bits/stdc++.h>
using namespace std;
#define ULL unsigned long long
#define INF ~0ULL
ULL p[16] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53};
ULL ans;
ULL n;
// depth: 当前在枚举第几个素数。num: 当前因子数。
// temp: 当前因子数量为 num
// 的时候的数值。up：上一个素数的幂，这次应该小于等于这个幂次嘛
void dfs(ULL depth, ULL temp, ULL num, ULL up) {
if (num > n || depth >= 16) return;
if (num == n && ans > temp) {
ans = temp;
return;
}
for (int i = 1; i <= up; i++) {
if (temp / p[depth] > ans) break;
dfs(depth + 1, temp = temp * p[depth], num * (i + 1), i);
}
}
int main() {
while(scanf("%llu", &n) != EOF) {
ans = INF;
dfs(0, 1, 1, 64);
printf("%llu\n", ans);
}
return 0;
}
最大公约数
int gcd(int a, int b) {
if (b == 0) return a;
return gcd(b, a % b);
}
以上为欧几里得求法。时间复杂度为 $O(log$ $n)$。
多个数的最大公约数
- 那怎么求多个数的最大公约数呢？显然答案一定是每个数的约数，那么也一定是每相邻两个数的约数。我们采用归纳法，可以证明，每次取出两个数求出答案后再放回去，不会对所需要的答案造成影响。
扩展欧几里得定理
常用于求 $ax+by=gcd(a,b)$ 的一组可行解。
int Exgcd(int a, int b, int &x, int &y) {
if (!b) {
x = 1;
y = 0;
return a;
}
int d = Exgcd(b, a % b, x, y);
int t = x;
x = y;
y = t - (a / b) * y;
return d;
}
欧拉函数
定义
即 $φ(n)$，表示的是小于等于 $n$ 和 $n$ 互质的数的个数。
当 $n$ 是质数的时候，显然有 $φ(n)=n-1$。
一些性质
- 欧拉函数是积性函数。
如果有 $gcd(a,b)=1$，那么 $φ(a×b)=φ(a)×φ(b)$
当 $n$ 是奇数时，$φ(2n)=φ(n)$。
- 若 $n=p^k$，其中 $p$ 是质数，那么 $φ(n)=p^k-p^{k-1}$ 。
求欧拉函数值
int euler_phi(int n) {
int ans = n;
for (int i = 2; i * i <= n; i++)
if (n % i == 0) {
ans = ans / i * (i - 1);
while (n % i == 0) n /= i;
}
if (n > 1) ans = ans / n * (n - 1);
return ans;
}
欧拉定理
若 $gcd(a,m)=1$，则 $a^{φ(m)}≡1(mod$ $m)$。
扩展欧拉定理
素数筛法
埃氏筛法
int Eratosthenes(int n) {
int p = 0;
for (int i = 0; i <= n; ++i) is_prime[i] = 1;
is_prime[0] = is_prime[1] = 0;
for (int i = 2; i <= n; ++i) {
if (is_prime[i]) {
prime[p++] = i; // prime[p]是i,后置自增运算代表当前素数数量
if ((long long)i * i <= n)
for (int j = i * i; j <= n; j += i)
// 因为从 2 到 i - 1 的倍数我们之前筛过了，这里直接从 i
// 的倍数开始，提高了运行速度
is_prime[j] = 0; // 是i的倍数的均不是素数
}
}
return p;
}
时间复杂度为 $O(log$ $log$ $n)$。
欧拉筛法
void init() {
phi[1] = 1;
for (int i = 2; i < MAXN; ++i) {
if (!vis[i]) {
phi[i] = i - 1;
pri[cnt++] = i;
}
for (int j = 0; j < cnt; ++j) {
if (1ll * i * pri[j] >= MAXN) break;
vis[i * pri[j]] = 1;
if (i % pri[j]) {
phi[i * pri[j]] = phi[i] * (pri[j] - 1);
} else {
// i % pri[j] == 0
// 换言之，i 之前被 pri[j] 筛过了
// 由于 pri 里面质数是从小到大的，所以 i 乘上其他的质数的结果一定也是
// pri[j] 的倍数 它们都被筛过了，就不需要再筛了，所以这里直接 break
// 掉就好了
phi[i * pri[j]] = phi[i] * pri[j];
break;
}
}
}
}
时间复杂度为 $O(n)$。
裴蜀定理
设 $a,b$ 是不全为零的整数，则存在整数 $x,y$, 使得 $ax+by=gcd(a,b)$。
乘法逆元
如果一个线性同余方程 $ax≡1(mod$ $b)$，则 $x$ 称为 $a$ $mod$ $b$ 的逆元，记作 $a^{-1}$。
- 求出 $1,2,···,n$ 中每个数关于 $p$的逆元。
inv[1] = 1;
for (int i = 2; i <= n; ++i) {
inv[i] = (long long)(p - p / i) * inv[p % i] % p;
}
线性同余方程
形如 $ax≡c(mod$ $b)$ 的方程被称为线性同余方程。
方程 $ax+by=c$ 与方程 $ax≡c(mod$ $b)$ 是等价的。整数解的充要条件为 $gcd(a,b)|c$。
int ex_gcd(int a, int b, int& x, int& y) {
if (b == 0) {
x = 1;
y = 0;
return a;
}
int d = ex_gcd(b, a % b, x, y);
int temp = x;
x = y;
y = temp - a / b * y;
return d;
}
bool liEu(int a, int b, int c, int& x, int& y) {
int d = ex_gcd(a, b, x, y);
if (c % d != 0) return 0;
int k = c / d;
x *= k;
y *= k;
return 1;
}
关于作者Zhang, Xuheng
- 还没有填写个人简介
- Email: hy23682@126.com
- 注册于: 2020-04-07 05:11:14
qp