质数与约数
质数
质数和合数的概念只针对于大于1的整数成立。
质数：在大于1的整数中，如果只包含1和本身这两个约数，就被称为质数，或者素数。
质数的判定
试除法
bool is_prime(int n)
{
if(n < 2) return false;
for(int i = 2; i < n; i ++)
{
if(n % i == 0) return false;
}
return true;
}
因此在枚举的过程中，我们可以只枚举较小的那个数，即\(d\leq\frac{n}{d},d^2\leq n, d\leq\sqrt{n}\)，
试除法判定质数算法模板
\(O(\sqrt{n})\)
bool is_prime(int x)
{
if (x < 2) return false;
for (int i = 2; i <= x / i; i ++ )
if (x % i == 0)
return false;
return true;
}
分解质因数
试除法
从小到大枚举所有的数，判断是否能被整除从而枚举所有质因数\(O(n)\)
void divide(int n)
{
for(int i = 2; i <= n; i ++)
{
if(n % i == 0)
{
int s = 0;
while(n % i == 0)
{
n /= i;
s ++;
}
printf("%d %d\n", i, s);
}
}
}
n中最多只包含一个大于\(\sqrt{n}\)的质因子（假如有两个大于\(\sqrt{n}\)的质因子，乘起来就会大于n）
因此只需要枚举2到\(\sqrt{n}\)，在判断最后剩下来的数是否为1，不为1说明是大于\(\sqrt{n}\)的质因子并输出，优化为\(O(\sqrt{n})\)
试除法分解质因数算法模板
void divide(int x)
{
for (int i = 2; i <= x / i; i ++ )
if (x % i == 0) // i 一定是质数
{
int s = 0;
while (x % i == 0) x /= i, s ++ ;
printf("%d %d\n", i, s);
}
if (x > 1) printf("%d 1\n", x);
cout << endl;
}
筛法
朴素筛法
当\(i=2\)时，循环\(\frac{n}{2}\)次
当\(i=3\)时，循环\(\frac{3}{n}\)次
\[\frac{n}{2}+\frac{n}{3}+...+\frac{n}{n}=n(\frac{1}{2}+\frac{1}{3}+...+\frac{1}{n})\\ 1+\frac{1}{2}+\frac{1}{3}+...+\frac{1}{n} = lnn + c\\ \therefore \frac{n}{2}+\frac{n}{3}+...+\frac{n}{n}=nlnn<nlogn \]\(O(nlogn)\)
朴素筛法求素数算法模板
int primes[N], cnt; // primes[]存储所有素数
bool st[N]; // st[x]存储x是否被筛掉,m
void get_primes(int n)
{
for(int i = 2; i <= n; i ++)
{
if(!st[i])
{
primes[cnt ++] = n;
}
for(int j = i + i; j <= n; j += i)
st[j] = true;
}
}
埃氏筛法
如果我们留下了\(p\)，说明\(p\)是一个质数。
对于合数来说，它的倍数也一定被这个合数的因此筛掉了，所有不用再考虑筛合数的倍数
我们可以只删所有质数的倍数，对于非质数，我们不需要删他的倍数
质数定理：\(1-n\)中有\(\frac{n}{lnn}\)个质数
优化为\(O(nloglogn)\)
埃氏筛法求素数算法模板
int primes[N], cnt; // primes[]存储所有素数
bool st[N]; // st[x]存储x是否被筛掉
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;
}
}
欧拉(线性)筛法
每个数\(n\)只会被最小质因子筛掉
循环里面有两种情况：
- \(i\%primes[j]==0\)， \(primes[j]\)一定是\(i\)的最小质因子，\(primes[j]\)一定是\(primes[j]\times i\)的最小质因子
- \(i\%primes[j]!=0\)， \(primes[j]\)一定小于\(i\)的所有最小质因子，\(primes[j]\)也一定是\(primes[j]\times i\)的最小质因子
对于一个合数x，假设\(primes[j]\)是\(x\)的最小质因子，当\(i\)枚举到\(x/primes[j]\)的时候，就会被筛掉
所以，每个数只会被他的最小质因子筛掉，只会被筛一次
可以通过算术基本定理来理解
\(O(n)\)
线性筛法求素数算法模板
int primes[N], cnt; // primes[]存储所有素数
bool st[N]; // st[x]存储x是否被筛掉
void 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; // primes[j]一定是i的最小质因子
}
}
}
约数
试除法求约数
试除法求所有约数算法模板
vector<int> get_divisors(int x)
{
vector<int> res;
for (int i = 1; i <= x / i; i ++ )
if (x % i == 0)
{
res.push_back(i);
if (i != x / i) res.push_back(x / i);
}
sort(res.begin(), res.end());
return res;
}
约数个数
基于算术基本定理
\[N=p_1^{\alpha 1}\times p_2^{\alpha 2}\times ... \times p_n^{\alpha n}\\ 约数个数:(\alpha_1+1)\times (\alpha_2+1) \times ... \times (\alpha_n+1)\\ 证明如下:\\ 设m为N的约数\\ 又\because N=p_1^{\alpha 1}\times p_2^{\alpha 2}\times ... \times p_n^{\alpha n}\\ \therefore m=p_1^{\beta 1}\times p_2^{\beta 2}\times ... \times p_n^{\beta n}(\beta_i \in{0,1,...,\alpha_i})\\ \therefore \beta_1有\alpha_1+1种选法，...,\beta_n有\alpha_n+1种选法\\ 由分步乘法计数原理\\ m有(\alpha_1+1)\times (\alpha_2+1) \times ... \times (\alpha_n+1)种选法 \]约数之和
\[N=p_1^{\alpha 1}\times p_2^{\alpha 2}\times ... \times p_n^{\alpha n}\\ 约数之和:(p_1^0+p_1^1+...p_1^{\alpha_1})\times ... \times (p_k^0+p_k^1+...p_k^{\alpha_k})\\ (乘法分配律展开) \]\[72=2^3\times 3^2\\ 约数个数:(3+1)\times (2+1) = 12\\ 1,2,4,8\\1,3,9\\6,12,18,24,36,72\\ 1\times (1+3^1+3^2)+2\times (1+3^1+3^2)+2^2\times (1+3^1+3^2)+2^3\times (1+3^1+3^2)=(1+2+2^2+2^3)\times(1+3+3^2)\\ \]约数个数和约数之和算法模板
如果 N = p1^c1 * p2^c2 * ... *pk^ck
约数个数： (c1 + 1) * (c2 + 1) * ... * (ck + 1)
约数之和： (p1^0 + p1^1 + ... + p1^c1) * ... * (pk^0 + pk^1 + ... + pk^ck)
// 质因数分解,存储在map中
void divide(int n)
{
for(int i = 2; i <= n / i; i ++)
{
if(n % i == 0)
{
int s = 0;
while(n % i == 0) n /= i, s ++;
mp[i] += s;
}
}
if(n != 1) mp[n] ++;
}
// 约数个数
for(auto p : mp)
{
ans = (ans * (p.second + 1) % mod) % mod;
}
// 约数之和
for(auto p : mp)
{
long long num = 1;
for(int i = 0; i < p.second; i ++)
{
num = (num * p.first + 1) % mod;
}
ans = (ans * (num % mod)) % mod;
}
欧几里得算法
\[\because d|a,d|b\\ \therefore d|a+b,d|ax+by\\ a\%b=a-\lfloor\frac{a}{b}\rfloor*b=a-c*b\\ (a,b)=(b,a\%b)=(b,a-c*b)\\ \]欧几里得算法算法模板
int gcd(int a, int b)
{
return b ? gcd(b, a % b) : a;
}