质数相关
一、算数基本定理
任何一个大于1的正整数都能唯一分解成有限个质数的乘积
写作：
\[ n=p_1^{c1}p_2^{c2}\dots p_m^{cm} \]\[ =\prod_{i=1}^mp_i^{ci} \]二、因数分布
若存在一个正整数 $ n $ 为合数，则存在一个数 $ k $ ,满足 $ 2 $ $ \le $ $k \le $ $ \sqrt{n} $ 且 $ k|n $
证明：
首先证明一个结论：
如果 \(m_1 \times m_2=n\) ，那么，$ m_1 $ 和 $ m_2 $ 必定有一个大于 \(\sqrt{n}\)，一个小于 $ \sqrt{n} $ 。
假如我们在 $ 2-\sqrt{n}$ 没有找到 $ n $ 的因数，在 $ \sqrt{n}-n $ 中找到了因数 $ m_1 $ ,根据上面的结论，另一个因数 $ m_2 $ 肯定在 $ 2-\sqrt{n} $ 之间，与在 $ 2-\sqrt{n} $ 之间没有找到因数矛盾，命题获证。
三、素数筛
1.埃氏筛
原理：素数的倍数一定不是素数
code
for(int i=2;i<=n;++i)
if(isprime[i]==1)
{
for(int j=2*i;j<=n;j+=i)
isprime[j]=0;
}
埃氏筛的复杂度已经非常接近线性了，但是不能完全达到线性，因为它在筛的时候会有重复，比如说 \(12\)，它在被 \(2\) 筛过之后，循环到 \(3\) 的时候都会再重新筛一遍。
2.线性筛
针对上面的埃氏筛存在的问题，我们可以让每一个合数只被它的最小质因数筛掉。具体的，它通过 if(i%prime[j] == 0) break; 这一行来实现。
简单理解一下：i%prime[j] == 0 ，说明 \(\mathrm{i}\) 有 \(\mathrm{prime_j}\) 这个因子。如果再往后循环，\(\mathrm{i \times prime_{j+1}}\) 这个数里有 \(\mathrm{prime_j}\) 这个因子，那么 \(\mathrm{prime_{j+1}}\) 就不是它的最小质因子了，所以 break。
code
#include<bits/stdc++.h>
#define int long long
#define ll long long
#define next nxt
#define re register
#define il inline
const int N = 1e7 + 5;
const int M = 1e8 + 5;
using namespace std;
int max(int x,int y){return x > y ? x : y;}
int min(int x,int y){return x < y ? x : y;}
bool isprime[M];
int n,q,k;
int cnt,prime[N];
il int read()
{
int f=0,s=0;
char ch=getchar();
for(;!isdigit(ch);ch=getchar()) f |= (ch=='-');
for(; isdigit(ch);ch=getchar()) s = (s<<1) + (s<<3) + (ch^48);
return f ? -s : s;
}
il void get_prime(int n)
{
memset(isprime , 1 , sizeof isprime);
isprime[1] = 0;
for(re int i=2;i<=n;i++)
{
if(isprime[i]) prime[++cnt] = i;
for(re int j=1;j<=cnt && i*prime[j]<=n;j++)
{
isprime[i*prime[j]] = 0;
if(i % prime[j] == 0) break;
}
}
}
signed main()
{
n = read() , q = read();
get_prime(n);
while(q--) k = read() , cout << prime[k] << "\n";
return 0;
}
}
四、一个正整数 $ n $ ,至多只有一个大于 $ \sqrt{n} $ 的质因子
证明：设 $ p,q≥ sqrt(n) $ ， $ p | n $ , $ q | n $ ,那么我们有 $ pq | n $ , $ pq > n $ , 很显然矛盾，命题获证。
约数
一、基础知识
带余除法
设 $ a $ , $ b $ 是两个整数，且 $ b \not= 0 $ ，如果存在整数 $ c $ ,则存在唯一的整数 $ q,r $ , 使得 $ a=qb+r (0\leq r < b)$ ，该式被
称为带余除法，并记 $ r=a\mod b $ 。
整除
定义
若整数 \(n\) 除以整数 \(d\) 的余数为 \(0\) ，即 \(d\) 能整除 \(n\) ，则称 \(d\) 是 \(n\) 的约数，计为 \(d\mid n\)。
性质
- 若 $ a \mid b $ 且 $ a \mid c $ ，则 $ \forall x,y $ ，有 $ a \mid xb+yc $ 。
证明：
把 \(b\) 和 \(c\) 里的 \(a\) 提出来乘法分配一下就行了。
设 $ b=an, c=am $ ，则 $ xb+yc=xan+yam=a(xn+ym) $ ，很明显 $ a \mid a(xn+ym) $ ，命题获证。
-
若 $ a \mid b , b \mid c $ ，则 $ a \mid c $ 。（传递性）
-
若 $ ma \mid mb (m \ne 0) $ ，则 $ a \mid b $ 。
-
若 $ a \mid b $ 且 $ b \mid a $ ，则 $ a=\pm b $ 。
二、算术基本定理的推论
对于唯一分解的正整数 $ n= p_1{c_1}p_2\dots p_m^{c_m} $
其正约数集合可写作 $ { p_1{c_1}p_2 \dots p_m^{b_m}}$，其中 $0 \le b_i \le c_i $
- 其正约数个数为：
证明一下：关于这个数 \(n\) ，仅和质因子 \(p_i\) 及其幂次方有关的因子有 \(c_i+1\)个(\(1,p_i,p_i^1,p_i^2\dots p_i^{c_i}\)) ，根据乘法原理，正约数个数就是 \(\prod_{i=1}^m(c_i+1)\)。
然后我们可以线性筛出来(
思路
设 \(a_i\) 记录 \(i\) 的最小质因子的次数，\(d_i\) 记录 \(i\) 的约数个数。
若 \(i\) 是质数，\(a_i = 1,d_i=2\)。
我们知道，每个合数 \(n\) 都是被最小的质因子筛掉的。设 \(p_j\) 是 \(n\) 的最小质因子，那么 \(n\) 会通过 \(p_j \times i\) 被筛掉，这就产生两种情况：
-
- 若 \(i\) 能被 \(p_j\) 整除，则 \(p_j\) 一定也是 \(i\) 的最小质因子①。\(a_n = a_i + 1\)。又因为 \(d_i = (a_i+1)\times \dots , d_n = (a_n+1)\times \dots\) ，变化的只有第一项。
所以
a[n] = a[i]+1,d[n] = d[i]/a[n]*(a[n]+1) -
- 若 \(i\) 不能被 \(p_j\) 整除，则 \(p_j\) 不是 \(i\) 的最小质因子。所以 \(n\) 质因数分解后的第一个质因子就不是 \(i\) 分解后的第一个质因子了，而变成了 \(p_j\) ，所以式子中加了一项。
所以
a[n] = 1,d[n] = d[i]*(1+1)
①：反证法证明，若 \(i\) 的最小质因子不是 \(p_j\) ，那么 \(n = i \times p_j\) 的最小质因子肯定也不是 \(p_j\) ，不满足每个合数都被最小质因子筛掉，故 \(p_j\) 也是 \(i\) 的最小质因子。
Code
int a[N]; //a[i]记录i的最小质因子的次数
int d[N]; //d[i]记录i的约数个数
int prime[N],cnt;
bool isprime[N];
il void get_d(int n)
{
memset(isprime , 1 ,sizeof isprime);
isprime[1]=0; d[1] = 1;
for(int i=2;i<=n;i++)
{
if(isprime[i])
{
prime[++cnt]=i;
a[i] = 1 , d[i] = 2;
}
for(int j=1;j<=cnt && prime[j]*i <=n ;j++)
{
int m = i*prime[j];
isprime[m]=0;
if(i%prime[j] == 0)
{
a[m] = a[i] + 1;
d[m] = d[i]/a[m]*(a[m]+1);
break;
}
else a[m] = 1 , d[m] = d[i]*2;
}
}
}
- 其所有约数和为：
这个也能筛出来(
思路
设 \(g_i\) 表示 \(i\) 的最小质因子的 \(1+p^1+p^2+\dots +p^k\)，\(f_i\) 记录 \(i\) 的约数和。
若 \(i\) 是质数，\(g_i = f_i = i+1\)。
还是类似的两种情况：
-
- 若 \(i\) 能被 \(p_j\) 整除，则 \(p_j\) 一定也是 \(i\) 的最小质因子。\(g_i = p_j^0 + p_j^1 + \dots +p_j^k\) ，\(g_n = p_j^0 + p_j^1 + \dots + p_j^{k+1}\) ，我们不好维护 \(k\) 。
我们把 \(g_n\) 的后 \(k\) 项同时提出来一个 \(p_j\) , \(g_n\) 就变成了 \(p_j^0 + p_j(p_j^0 + p_j^1 + \dots +p_j^k)\) ，我们发现括号里面就是 \(g_i\) ，这样就巧妙地解决了问题。
所以
g[n] = g[i] * p[j] + 1 , f[n] = f[i] / g[i] * g[n]。 - 若 \(i\) 能被 \(p_j\) 整除，则 \(p_j\) 一定也是 \(i\) 的最小质因子。\(g_i = p_j^0 + p_j^1 + \dots +p_j^k\) ，\(g_n = p_j^0 + p_j^1 + \dots + p_j^{k+1}\) ，我们不好维护 \(k\) 。
-
- 若 \(i\) 不能被 \(p_j\) 整除，则 \(p_j\) 不是 \(i\) 的最小质因子。所以同样的式子中加了一项。
所以
g[n] = p[j] + 1,f[n] = f[i]*g[n]
Code
//g[i]表示i的最小质因子的1+p^1+...+p^k
int g[N], f[N];//f[i]表示i的约数和
int prime[N],cnt;
bool isprime[N];
il void get_f(int n)
{
memset(isprime , 1 ,sizeof isprime);
isprime[1]=0; g[1] = f[1] = 1;
for(int i=2;i<=n;i++)
{
if(isprime[i])
{
prime[++cnt]=i;
g[i] = f[i] = i+1;
}
for(int j=1;j<=cnt && prime[j]*i <=n ;j++)
{
int m = i*prime[j];
isprime[m]=0;
if(i%prime[j] == 0)
{
g[m] = g[i]*prime[j]+1;
f[m] = f[i]/g[i]*g[m];
break;
}
else g[m] = p[j]+1 , d[m] = f[i]*g[m];
}
}
}
- 对于一个合数 $ n^2 $ ，它的约数个数为：
很好理解，因为 \(n^2\) 中每个质因子的幂次都是 \(n\) 的 \(2\) 倍 ，所以就是 \(c_i \times 2 + 1\) 。
三、求 \(N\) 的正约数集合
- 试除法
因为约数成对出现(除了完全平方数的 \(\sqrt{n}\)单独出现)。
所以我们只需要扫描 \(1-\sqrt{n}\),尝试能否整除 \(n\) 即可，时间复杂度 \(O(\sqrt{n})\)
由试除法引出的推论：一个整数 \(N\) 的约数个数上界为 \(2\sqrt{n}\)
- 倍数法
若想求 \(1-N\) 以内所有数的约数个数 , 若用试除法，复杂度是 \(O(n\sqrt{n})\) ，太高。为此我们用到倍数法：\(1-n\)中以 \(d\) 为约数的数就是\(d\)的倍数 \(d,2d,3d\dots \lfloor \frac{n}{d}\rfloor \times d\) ，用这个来求。
Code
vector <int> factor[500005];
for(re int i=1;i<=n;i++)
for(re int j=1;j<=n/i;j++)
factor[i*j].push_back(i);
for(re int i=1;i<=n;i++)
{
for(re int j=0;j<factor[i].size();j++) cout << factor[i][j] << "";
cout << "\n";
}
时间复杂度为 \(O(N+N/2+N/3+\dots N/N) = O(NlogN)\)
由倍数法引出的推论：\(1-N\) 的约数个数总和大约为 \(NlogN\)
四、最大公约数和最小公倍数
性质：
-
- \(a \times b = \gcd(a,b) \times \text{lcm}(a,b)\)
证明：设 $a = p_1{a_1}p_2\dots p_m^{a_m} , b= p_1{b_1}p_2\dots p_m^{b_m} $
则 \(a \times b = p_1^{a_1+b_1}p_2^{a_2+b_2}\dots p_m^{a_m+b_m}\)
\(=p_1^{\min(a_1,b_1)+\max(a_1,b_1)}p_2^{\min(a_2,b_2)+\max(a_2,b_2)} \dots p_m^{\min(a_m,b_m)+\max(a_m,b_m)}\)
$ = \gcd(a,b) \times \text{lcm}(a,b)$
-
- 若 $a \mid m $ 且 \(b \mid m\) , 则 \(\text{lcm}(a,b) \mid m\)
\(c_m \geq \text{max}(c_a,c_b)\) ，所以自然而然 \(\text{lcm}(a,b) \mid m\)
-
- 若 $d \mid a $ 且 \(d \mid b\) , 则 \(d \mid \gcd(a,b)\)
\(c_d \leq \text{min}(c_a,c_b)\) ，所以自然而然 \(d \mid \text{gcd}(a,b)\)
-
- 若 \(a,b,m \in \mathbb{N}\) , 则 \(\text{lcm}(ma,mb) = m \times \text{lcm}(a,b)\)
-
- 更相减损术：
\(\forall a,b \in \mathbb{N}\) ，\(a\geq b\) ，有 \(\text{gcd}(a,b) = \text{gcd}(b,a-b) = \text{gcd}(a,a-b)\)
证明：对于 \(a,b\) 的任意公约数 \(d\) ，\(d \mid a, d\mid b\) ，根据整除性质1得，很容易构造 \(x=1,y=-1\) ,得到 \(d\mid (a-b)\) ，因此 \(d\) 也是 \(b,a-b\) 的约数。所以 \(a,b\) 的公约数集合和 \(b,a-b\) 的公约数集合相同，它们的最大公约数自然也相等。
-
- 欧几里得算法：
见数学(Ⅱ):同余相关
- 欧几里得算法：