写篇文章方便自己复习
玄学 数学知识笔记（一）：
1. 试除法判定指数
这个没什么难的就直接上代码了
#include <iostream>
using namespace std;
bool is_prime(int x)
{
if (x == 1) return false;//1需要特判
for (int i = 2; i <= x / i; i ++ )
if (x % i == 0) return false;
return true;
}
int main()
{
int x, n;
cin >> n;
while (n -- )
{
cin >> x;
if (is_prime(x)) puts("Yes");
else puts("No");
}
return 0;
}
唯一需要注意的一点就是循环内我们不写成 i * i <= x 是以免爆 $int$
2.分解质因数
核心思想是找到一个质因子就用一个循环把它除干净，并记录最多可以s次，s即为指数。需要特别注意一下最后x可能还没有分解干净，最后剩下来的x如果大于0，则x本身就是最后一个质因子，当然指数为1.
#include <iostream>
using namespace std;
void divide(int x)
{
for (int i = 2; i <= x / i; i ++ )
if (x % i == 0)
{
int s = 0;
while (x % i == 0)
{
s ++ ;
x /= i;
}
cout << i << ' ' << s << endl;
}
if (x > 1) cout << x << ' ' << 1 << endl;
}
int main()
{
int n, x;
cin >> n;
while (n -- )
{
cin >> x;
divide(x);
puts("");
}
return 0;
}
3.筛质数
普通的埃氏筛法(复杂度 $O(nloglogn)$)比较好理解，这里不再赘述，主要讲一下线性筛。
线性筛法核心：每个合数只会被自己的最小质因数筛掉，复杂度降为 $O(n)$
#include <iostream>
using namespace std;
const int N = 1e6 + 10;
int primes[N], cnt;
bool st[N];
int 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;
}
}
return cnt;
}
int main()
{
int n;
scanf("%d", &n);
cout << get_primes(n) << endl;
return 0;
}
将内层循环单独拎出来看：
for (int j = 0; primes[j] <= n / i; j ++ )
{
st[primes[j] * i] = true;//pj 为 pj * i 的最小质因数
if (i % primes[j] == 0)
break; //当 i % pj == 0 时则代表pj为i的最小质因数，因为pj是从大到小枚举的，根据
//线性筛的核心是每个合数只会被自己的最小质因数筛掉筛掉，这时退出循环即可
}
4.试除法求约数
这个就比较简单了，只需要注意当遍历到一个约数 $i$ 时，其对应的 $n / i$ 这个约数也确定了，所以可以在 $O(\sqrt{n})$ 的复杂度内求出所有约数
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
void get_divisors(int x)
{
vector <int> res;
for (int i = 1; i <= x / i; i ++ )
if (x % i == 0)
{
res.push_back(i);
if (x / i != i) res.push_back(x / i);
}
sort(res.begin(), res.end());
for (int i = 0; i < res.size(); i ++ ) cout << res[i] << ' ';
}
int main()
{
int n, x;
cin >> n;
while (n -- )
{
cin >> x;
get_divisors(x);
cout << endl;
}
return 0;
}
5.约数个数
这个算法依赖于我们 小学二年级就学过的 约数个数定理，忘了的同学可以翻翻课本：小学二年级课本
对于一个大于1的正整数n可以分解质因数：
$$n=\prod\limits_{i=1}^{k}{p_i}^{a_i}={p_1}^{a_1}·{p_2}^{a_2}·····{p_k}^{a_k}$$
则n的正约数的个数为：
$$f(n)=\prod\limits_{i=1}^{k}(a_i+1)=(a_1+1)(a_2+1)···(a_k+1)$$
证明过程可以看看课本，代码如下：
#include <iostream>
#include <unordered_map>
#include <algorithm>
using namespace std;
const int mod = 1e9 + 7;
unordered_map <int, int> primes;
typedef long long LL;
void divide(int x)
{
for (int i = 2; i <= x / i; i ++ )
while (x % i == 0)
{
primes[i] ++ ;
x /= i;
}
if (x > 1) primes[x] ++ ;
}
int main()
{
int n, x;
cin >> n;
while (n -- )
{
cin >> x;
divide(x);
}
LL ans = 1;
for (auto i : primes) ans = ans * (i.second + 1) % mod;
cout << ans << endl;
return 0;
}
6.约数之和
同样依赖于定理： 约数和定理
还是对于一个大于1的正整数n分解质因数：
$$n=\prod\limits_{i=1}^{k}{p_i}^{a_i}={p_1}^{a_1}·{p_2}^{a_2}·····{p_k}^{a_k}$$
则它所有约数之和为：
$$f(n)=({p_1}^0+{p_1}^1+···+{p_1}^{a_1})({p_2}^0+{p_2}^1+···+{p_2}^{a_2})···({p_k}^0+{p_k}^1+···+{p_k}^{a_k})$$
注意到这道题要我们求的是给出的数的乘积的约数之和，其实就是每个数分别分解质因数，将它们的指数累加起来，最后用公式算出答案。
那如何算出最后的答案呢？这里就运用到了一个巧妙的方法(来源于秦九韶算法)
对于一个质因子 p，指数为 s，一开始令 $t=1$ ，每次乘上一个 $p$ 再加上一个 $1$，可以得到如下转换：$$
t = 1$$$$
t = 1·p+1 = p+1$$$$
t = p·(p + 1) + 1 = p^2 + p + 1$$$$
......$$$$
t = p^s + p^{s-1} +···+ p + 1$$
是不是很神奇呢？ 代码如下：
#include <iostream>
#include <unordered_map>
#include <algorithm>
using namespace std;
unordered_map <int, int> primes;
typedef long long LL;
const int mod = 1e9 + 7;
void get_divisors(int x)
{
for (int i = 2; i <= x / i; i ++ )
while (x % i == 0)
{
x /= i;
primes[i] ++ ;
}
if (x > 1) primes[x] ++ ;
}
int main()
{
int n, x;
cin >> n;
while (n -- )
{
cin >> x;
get_divisors(x);
}
LL res = 1;
for (auto x : primes)
{
int p = x.first, s = x.second;
LL t = 1;
while (s -- ) t = (t * p + 1) % mod;
res = res * t % mod;
}
cout << res << endl;
return 0;
}
7.最大公约数
这可以说是这一章里面最简单的算法了qwq：欧几里得算法及其证明
假设 $a>b$ , 将 $a$ 与 $b$ 的最大公约数记作 $gcd(a, b)$ ($\mathtt{Greatest Common Divisor}$)，则有：
$ gcd(a,b) = gcd(b, a$ $mod$ $b) $
就这样递归求解直到后面一项为0，返回前面一项的值即可
#include <iostream>
using namespace std;
int gcd(int a, int b)
{
return b ? gcd(b, a % b) : a;
}
int main()
{
int n, x, y;
cin >> n;
while (n -- )
{
cin >> x >> y;
cout << gcd(x, y) << endl;
}
return 0;
}
