2022.01.31刷题
今天是除夕了 + acwing 第四讲.
质数
大于1 的整数中, 只包含1 和 本身这两个约数. 叫做质数或者素数.
试除法
直接从 试做到.sqrt(n)
int n, m;
bool is_prime(int n) {
if (n < 2) return false;
int sqrtn = sqrt(n);
for (int i = 2;i <= n / i;i++) {
if (n % i == 0) return false;
}
return true;
}
int main() {
m = read();
while (m--) {
puts(is_prime(read()) ? "Yes" : "No");
}
}
分解质因数
n中最多只包含一个大于sqrt(n)的质因子
int n, m;
void prime(int n) {
for (int i = 2;i <= n / i;i++) {
if (n % i == 0) {
int s = 0;
while (n % i == 0)s++, n /= i;
printf("%d %d\n", i, s);
}
}
if (n > 1) // 这里一定是 > 1 不是 > 2...
printf("%d %d\n", n, 1);
}
int main() {
m = read();
while (m--) {
prime(read());
puts("");
}
}
筛质数
筛法. 朴素做法
\(n(\frac12+\frac13+....+\frac1n)\)
\(=n(\ln n+c)\) c是欧拉常数. => nlogn ;
埃氏筛法: 改进. 删掉所有的质数的倍数.
质数定理 1~n中 有 \(\frac{n}{lnn}\)个质数.
O(n) O(nloglogn)的复杂度.
线性筛法:
正确性证明: 合数一定会被筛掉.
n 只会被最小质因子筛掉.
当prime[j] 是 i的最小质因子的时候, 就break;
任何一个数一定存在最小质因子, 所以一定会被筛掉.
int primes[N6], cnt;
bool st[N6];
void get_primes(int n) {
for (int i = 2;i <= n;i++) {
if (st[i]) continue;
primes[cnt++] = i;
for (int j = i + i;j <= n;j += i) {
st[j] = true; // 这里的判断其实是有一些被重复用了.
}
}
}
int main() {
get_primes(read());
O(cnt);
return 0;
}
约数
试除法求约数
和质因数一样, 到 sqrt(n)
然后特殊判断一下, 如果 i == n/i 只 push 一个就行
最后还需要对所以约数 sort 一下
约数个数
约数个数 是算数基本定理.
如果 \(N=p_1^{a1}\cdot p_2^{a2}...\)
则 个数是 \((a_1+1)(a_2+1)...(a_n+1)\)
int范围内, 约数最多的数 1500个 约数 可能是对的..
直接用 unordered_map 进行存储就行了
约数之和
\(=(p_1^0+p_1^1+p_1^2)....\) 每一个都乘起来.
while(a--) ..t=p*t+1 如何求上面的.
最大公约数
欧几里得算法.辗转相除法.
\(d|a\) \(d|b\) => \(d|(ax+by)\) a的若干倍+ b的若干倍
\((a,b) = (b,a\%b)\)
\((a,b) = (b,a-c \cdot b)\) 所以 根据上面可以的出来.
\(d|0\) 永远成立..
欧拉函数
欧拉函数
1 ~ N 中和 N 互质的数的个数.
\(N = p_1^{a_1}p_2^{a_2}…p_m^{a_m}\)
\(\phi(N) = N \times \frac{p_1-1}{p_1} \times \frac{p_2-1}{p_2} \times … \times \frac{p_m-1}{p_m}\)
如何求:
- 从1~N中去掉 p1 p2 ... pk 的倍数.
- 加上所有
pi * pj的倍数 - 去掉所有..... 加上...
容斥原理....
筛法求欧拉函数
快速幂
快速幂
快速幂求逆元
扩展欧几里得算法
扩展欧几里得算法
线性同余方程