筛法¶
质数筛法¶
定义¶
朴素筛法¶
对于每个数，筛掉他的所有倍数
复杂度：2要筛n / 2 次，3要筛n / 3次，所以一共要筛n / 2 + n / 3 + …n / n，也就是 n * (1 / 2 + 1 / 3 + … + 1 / n)次，后面求和是调和级数，当 n 足够大时，等于lnn + c，c是常数,所以复杂度为 logn * n.
埃氏筛法¶
复杂度：质数定理：1 - n 中质数的数量是 n / lnn 个，所以埃氏筛法的复杂度为 n * loglog n，很接近线性了。
代码实现
#include<bits/stdc++.h>
using namespace std;
int n,cnt,prime[100001],notprime[100001];
void erat(int n){
for(int i=2;i<=n;i++)
if(!notprime[i]){
prime[++cnt]=i;
for(int j=2;j<=n/i;j++){
notprime[j*i]=1;
}
}
}
signed main(){
cin>>n;
erat(n);
for(int i=1;i<=cnt;i++)cout<<prime[i]<<' ';
}
线性筛¶
线性筛法的核心是：n 只会被最小质因子筛掉，复杂度 O(n) 。
那么这是怎么做到的？
我们首先从2开始枚举每一个数，记\(ispri_i\)为数字i的最小因子（不含1）.
当\(ispri_i=0\)，说明i在之前都没有遇到它的因子，即i是质数。
无论i是否为质数，我们都需要使用它来标记一些数。什么从小到大枚举质数表里的质数\(pri_j\)，并且将\(i\times pri_j\)标记为非质数。此时\(pri_j\)也是它的ispri（最小真因数）。当我们枚举的\(pri_j>ispri_i\)时，我们就应该停止标记，因为后面的数显然可以被ispri_i标记。
为什么这样标记就可以做到不重复不遗漏呢？首先因为\(pri_j>ispri_i\)时，我们就停止标记，所以不会重复标记。又因为对于一个合数x，记其最小质因数为p，那么我们一定会在枚举到x/p时将x标记。因为\(ispri_{x/p}≥p\)，所以我们一定会枚举到p。
为了降低时间复杂度，我们在\(pri_j>N/i\)时也停止。
例如 在埃氏筛中 6 会被 2 和 3 都筛一遍，增加了复杂度
代码中两种情况的解释：
当 i % pj = 0 时，$p_j $一定是 $i $ 的最小质因子，因此 \(p_j\) 一定是 \(p_j\) * i 的最小质因子。 当 i % pj ≠ 0 时，\(p_j\) 一定小于 $ i$ 的最小质因子，因此 \(p_j\)一定是 \(p_j\) * i 的最小质因子。
代码实现
#include<bits/stdc++.h>
using namespace std;
int n,cnt,prime[100001],notprime[100001];
void oula(int n){
for(int i=2;i<=n;i++){
if(!notprime[i]){
prime[++cnt]=i;
notprime[i]=i;
}
for(int j=1;j<=cnt;j++){
if(prime[j]>notprime[i]||prime[j]>n/i)break;
notprime[i*prime[j]]=prime[j];
}
}
}
signed main(){
cin>>n;
oula(n);
for(int i=1;i<=cnt;i++)cout<<prime[i]<<' ';
}
当notprime[i] = i时,说明i是质数,反之存i的最小质因子.
i从 \(2 \to n\) 递增, 每次到达一个 \(i\) , 筛去数 \(i \times p\) (即将notprime[i*p]赋值为p), 其中 \(p≤notprime[i]\) 且为质数
优化算法
例题
算法
【算法/数论】欧拉筛法详解：过程详述、正确性证明、复杂度证明_seh_sjlj的博客-CSDN博客
#include<bits/stdc++.h>
using namespace std;
const int N=1e8+5;
int notprime[N],q;
bool isprime[N]; // isprime[i]表示i是不是素数
int prime[N]; // 现在已经筛出的素数列表
int n; // 上限，即筛出<=n的素数
int cnt; // 已经筛出的素数个数
void euler()
{
memset(isprime, true, sizeof(isprime)); // 先全部标记为素数
isprime[1] = false; // 1不是素数
for(int i = 2; i <= n; ++i) // i从2循环到n（外层循环）
{
if(isprime[i]) prime[++cnt] = i;
// 如果i没有被前面的数筛掉，则i是素数
for(int j = 1; j <= cnt && i * prime[j] <= n; ++j)
// 筛掉i的素数倍，即i的prime[j]倍
// j循环枚举现在已经筛出的素数（内层循环）
{
isprime[i * prime[j]] = false;
// 倍数标记为合数，也就是i用prime[j]把i * prime[j]筛掉了
if(i % prime[j] == 0) break;
// 最神奇的一句话，如果i整除prime[j]，退出循环
// 这样可以保证线性的时间复杂度
}
}
}
signed main(){
cin>>n>>q;
euler();
while(q--){
int k;
cin>>k;
cout<<prime[k]<<endl;
}
}
欧拉函数筛¶
欧拉函数¶
即 \(\varphi(n)\)，表示的是小于等于 n 且和 n 互质的数的个数。 比如说 \(\varphi(1) = 1\)。
若 m 是素数，则\(\varphi(m)=m-1\)
若m=pq，其中p,q是质数且p≠q，则\(\varphi(m)=(p-1)(q-1)\)
若\(m=\prod p_i^{l_i}\)，即质因数分解，那么\(\varphi(m)=m\times \prod (1-\frac{1}{p_i})\)
欧拉函数是**积性函数**。 即对任意满足\(\gcd(a,b)=1\)的整数a，b，有\(\varphi(ab)=\varphi(a)\varphi(b)\)。
求单点欧拉函数
int getphi(int x){
int res=x;
for(int i=2;i*i<=x;i++){
if(x%i==0){
res=res/i*(i-1);
while(x%i==0)x/=i;
}
}
if(x>1)res=res/x*(x-1);
return res;
}
//筛出质数后的版本
int phi(int x){
//按题目特判x=1的情况！
int t=x;
int a=1,b=1;
for(int i=1;i<=tot;i++){
if(pri[i]*pri[i]>x)break;
if(x%pri[i])continue;
a*=(pri[i]-1);
b*=(pri[i]);
while(x%pri[i]==0)x/=pri[i];
}
if(x>1){
a*=(x-1);
b*=x;
}
return t/b*a;
}
筛法求欧拉函数¶
什么考虑用线性筛来快速求出\(1\sim n\)之间的欧拉函数。如果x是质数，那么\(\varphi(x)=x-1\)。否则我们考虑在筛到\(pri_j\times i=x\)时将\(\varphi(x)\)求出来。
因为欧拉函数是极性函数，所以当i和\(pri_j\)互质时，\(\varphi(x)=\varphi(i)\times \varphi(pri_j)\)。那么当i和\(pri_j\)不互质时，就到了我们的退出条件（因为我们是从小到大枚举pri，因此第一次遇到不互质时说明\(ispri_i=pri_j\)，再往后就是\(ispri_i>pri_j\)了），此时\(\varphi(x)=\varphi(i)\times pri_j\)。为什么呢？
\(\varphi(x)=x\times \prod (1-\frac{1}{p_i})=pri_j\times i\times \prod (1-\frac{1}{p_i})=pri_j\times \varphi(i)\)，注意这里的\(\prod (1-\frac{1}{p_i})\)和因子（\(p_i\)）的个数无关，只和它的值的种类有关，又因为x,i的因子的值的种类相同，所以上式成立。
int prime[N],notprime[N];
int cnt;
int phi[N];
void init(){
phi[1]=1;
for(int i=2;i<N;i++){
if(!ispri[i]){
ispri[i]=i;
pri[++tot]=i;
phi[i]=i-1;
}
for(int j=1;j<=tot;j++){
if(pri[j]*i>=N)break;
if(i%pri[j]==0){
phi[i*pri[j]]=phi[i]*pri[j];
ispri[i*pri[j]]=pri[j];
break;
}
ispri[i*pri[j]]=pri[j];
phi[i*pri[j]]=phi[i]*phi[pri[j]];
}
}
}
例题 #1 [HAOI2012] 外星人¶
题目描述
艾莉欧在她的被子上发现了一个数字 \(N\)，她觉得只要找出最小的 \(x\) 使得，\(\varphi^x(N) = 1\)。根据这个 \(x\) 她就能找到曾经绑架她的外星人的线索了。当然，她是不会去算，请你帮助她算出最小的 \(x\)。
输入格式
第一行一个正整数 \(\mathrm{test}\)，接下来 \(\mathrm{test}\) 组数据每组数据第一行一个正整数 \(m\)，接下来 \(m\) 行每行两个正整数 \(p_i, q_i\)
其中 \(\displaystyle \prod_{i = 1}^{m} p_i^{q_i}\) 为 \(N\) 的标准分解形式。
\(\prod\) 为连乘
\(\varphi^x(N)\) 表示嵌套 \(x\) 次，不是幂
输出格式
输出 \(\mathrm{test}\) 行，每行一个整数，表示答案。
\(100\%\) 的数据，\(\mathrm{test} \le 50\)，\(1 \le p_i \le {10}^5\)，\(1 \le q_i \le {10}^9\)，\(m \le 2000\)。
\(\varphi\) 为欧拉函数，\(\varphi(n)\) 即小于等于 \(n\) 的数中与 \(n\) 互质的数的个数。
提示：\(\varphi(\prod_{i=1}^mp_i^{q_i})=\prod_{i=1}^m(p_i-1)*p_i^{q_i-1}\)。
首先我们就直接考虑对\(D=\prod_{i=1}^m(p_i-1)*p_i^{q_i-1}\)做到最小的x使得\(\varphi^x(D)=1\)。
那么我们发现D的因数都在10^5为内，我们可以考虑用欧拉函数的唯一分解定理式求解。我们发现递归的本质是每次执行下面的操作：
对于D的每一个质因数\(p^q\)，将其变成\((p-1)\times p^{q-1}\)。注意-1后的数不再是质数。问多少次操作可以使得D变成2或者1.
模拟是不可能的，并且因为一个数-1或变成哪些数字也需要很高的复杂度来统计，所以我们需要转换思路。
我们考虑若最开始的D不是2的倍数，那么从第2次操作开始一定又2的倍数，否则从第一次开始就有。并且每一次操作最多消去一个2，所以我们只需要统计一开始的D的所有因数可以产生多少个2即可。
那么我们设\(f_i\)为因数i可以产生的2的个数，那么若i是质数，则\(f_i=f_{i-1}\)。因为i自己不可被分解，只有-1后变成i-1才可以被分解，这和i-1直接分解是一样的。
如果i不是质数，那么设\(i=a\times b\)，那么\(f_i=f_a+f_b\)。为什么呢？还是横显然的吧。
因此我们像筛phi一样筛f即可。最后\(p^q\)的贡献为\(f_p\times q\)。注意，如果存在p=2，那么答案-1.
不要忘记最开始的那次操作。
/*
Keyblinds Guide
###################
@Ntsc 2024
- Ctrl+Alt+G then P : Enter luogu problem details
- Ctrl+Alt+B : Run all cases in CPH
- ctrl+D : choose this and dump to the next
- ctrl+Shift+L : choose all like this
- ctrl+K then ctrl+W: close all
- Alt+la/ra : move mouse to pre/nxt pos'
*/
#include <bits/stdc++.h>
#include <queue>
using namespace std;
#define rep(i, l, r) for (int i = l, END##i = r; i <= END##i; ++i)
#define per(i, r, l) for (int i = r, END##i = l; i >= END##i; --i)
#define pb push_back
#define mp make_pair
#define int long long
#define ull unsigned long long
#define pii pair<int, int>
#define ps second
#define pf first
// #define innt int
#define itn int
// #define inr intw
// #define mian main
// #define iont int
#define rd read()
int read(){
int xx = 0, ff = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {
if (ch == '-')
ff = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9')
xx = xx * 10 + (ch - '0'), ch = getchar();
return xx * ff;
}
void write(int out) {
if (out < 0)
putchar('-'), out = -out;
if (out > 9)
write(out / 10);
putchar(out % 10 + '0');
}
#define ell dbg('\n')
const char el='\n';
const bool enable_dbg = 1;
template <typename T,typename... Args>
void dbg(T s,Args... args) {
if constexpr (enable_dbg){
cerr << s;
if(1)cerr<<' ';
if constexpr (sizeof...(Args))
dbg(args...);
}
}
#define zerol = 1
#ifdef zerol
#define cdbg(x...) do { cerr << #x << " -> "; err(x); } while (0)
void err() { cerr << endl; }
template<template<typename...> class T, typename t, typename... A>
void err(T<t> a, A... x) { for (auto v: a) cerr << v << ' '; err(x...); }
template<typename T, typename... A>
void err(T a, A... x) { cerr << a << ' '; err(x...); }
#else
#define dbg(...)
#endif
const int N = 1e6 + 5;
const int INF = 1e18;
const int M = 1e5;
const int MOD =999911659;
int f[N],pri[N],ispri[N];
int tot;
void init(){
f[1]=1;
for(int i=2;i<N;i++){
if(!ispri[i]){
ispri[i]=i;
pri[++tot]=i;
f[i]=f[i-1];
}
for(int j=1;j<=tot;j++){
if(pri[j]*i>=N)break;
f[i*pri[j]]=f[pri[j]]+f[i];
ispri[i*pri[j]]=pri[j];
if(i%pri[j]==0){
break;
}
}
}
}
itn ans=0;
void solve(){
int m=rd;
ans=0;
for(int i=1;i<=m;i++){
int p=rd,q=rd;
if(p==2)ans--;
ans+=f[p]*q;
}
cout<<ans+1<<endl;
}
signed main() {
// freopen(".in","r",stdin);
// freopen(".in","w",stdout);
init();
int T=rd;
while(T--){
solve();
}
return 0;
}
莫比乌斯函数筛¶
莫比乌斯函数¶
\(\mu(x)=\begin{cases}0 &\exist d_i\geq 1 \\(-1)^k & \forall d_i=1\end{cases}\)，\(d_i\)是x的质因子的次幂，k是x的质因子的个数。