4.1 质数
试除法判定质数 —— 模板题 AcWing 866. 试除法判定质数
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; }
试除法分解质因数 —— 模板题 AcWing 867. 分解质因数
void divide(int x) { for (int i = 2; i <= x / i; i ++ ) if (x % i == 0) { int s = 0; while (x % i == 0) x /= i, s ++ ; cout << i << ' ' << s << endl; } if (x > 1) cout << x << ' ' << 1 << endl; cout << endl; }
朴素筛法求素数 —— 模板题 AcWing 868. 筛质数
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; } }
线性筛法求素数 —— 模板题 AcWing 868. 筛质数
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; } } }
4.1.1 866. 试除法判定质数
给定 n 个正整数 ai，判定每个数是否是质数。
输入格式
第一行包含整数 n。
接下来 n 行，每行包含一个正整数 ai。
输出格式
共 n 行，其中第 i 行输出第 i 个正整数 ai 是否为质数，是则输出 Yes，否则输出 No。
数据范围
1≤n≤100,
1≤ai≤231−1
输入样例：
2
2
6
输出样例：
Yes
No
#include<bits/stdc++.h> using namespace std; const int N=110; int n; int main() { cin>>n; while(n--) { int x; cin>>x; bool flag=true; for(int i=2;i<=x/i;i++) { if(x%i==0) { flag=false; break; } } if(flag&&x!=1) cout<<"Yes"<<endl; else cout<<"No"<<endl; } return 0; }
4.1.2 867. 分解质因数
给定 n 个正整数 ai，将每个数分解质因数，并按照质因数从小到大的顺序输出每个质因数的底数和指数。
输入格式
第一行包含整数 n。
接下来 n 行，每行包含一个正整数 ai。
输出格式
对于每个正整数 ai，按照从小到大的顺序输出其分解质因数后，每个质因数的底数和指数，每个底数和指数占一行。
每个正整数的质因数全部输出完毕后，输出一个空行。
数据范围
1≤n≤100,
1≤ai≤2×109
输入样例：
2
6
8
输出样例：
2 1
3 1
2 3
#include<bits/stdc++.h> using namespace std; int n=110; void getP(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; cout<<endl; } int main() { cin>>n; while(n--) { int x; cin>>x; getP(x); } return 0; }
4.1.3 868. 筛质数
给定一个正整数 n，请你求出 1∼n 中质数的个数。
输入格式
共一行，包含整数 n。
输出格式
共一行，包含一个整数，表示 1∼n 中质数的个数。
数据范围
1≤n≤106
输入样例：
8
输出样例：
4
#include<bits/stdc++.h> using namespace std; const int N=1000010; int primes[N],cnt; bool st[N]; 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; } } } int main() { int n; cin>>n; get_primes(n); cout<<cnt; return 0; }
4.2 约数
试除法求所有约数 —— 模板题 AcWing 869. 试除法求约数
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; }
约数个数和约数之和 —— 模板题 AcWing 870. 约数个数, AcWing 871. 约数之和
如果 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)
欧几里得算法 —— 模板题 AcWing 872. 最大公约数
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
4.2.1 869. 试除法求约数
给定 n 个正整数 ai，对于每个整数 ai，请你按照从小到大的顺序输出它的所有约数。
输入格式
第一行包含整数 n。
接下来 n 行，每行包含一个整数 ai。
输出格式
输出共 n 行，其中第 i 行输出第 i 个整数 ai 的所有约数。
数据范围
1≤n≤100,
2≤ai≤2×109
输入样例：
2
6
8
输出样例：
1 2 3 6
1 2 4 8
#include<bits/stdc++.h> using namespace std; int main() { int n; cin>>n; while(n--) { int x; cin>>x; set<int> st; for(int i=1;i<=x/i;i++) { if(x%i==0) { st.insert(i); st.insert(x/i); } } for(set<int>::iterator it=st.begin();it!=st.end();it++) { cout<<*it<<" "; } cout<<endl; } return 0; }
4.2.2 870. 约数个数
给定 n 个正整数 ai，请你输出这些数的乘积的约数个数，答案对 109+7 取模。
输入格式
第一行包含整数 n。
接下来 n 行，每行包含一个整数 ai。
输出格式
输出一个整数，表示所给正整数的乘积的约数个数，答案需对 109+7 取模。
数据范围
1≤n≤100,
1≤ai≤2×109
输入样例：
3
2
6
8
输出样例：
12
#include<bits/stdc++.h> using namespace std; const int mod=1e9+7; typedef long long LL; int main() { int n; cin>>n; map<int,int> primes; while(n--) { int x; cin>>x; for(int i=2;i<=x/i;i++) { while(x%i==0) { x/=i; primes[i]++; } } if(x>1) primes[x]++; } LL res=1; for(map<int,int>::iterator it=primes.begin();it!=primes.end();it++) { res=res*(it->second+1)%mod; } cout<<res%mod; return 0; }
4.2.3 871. 约数之和
给定 n 个正整数 ai，请你输出这些数的乘积的约数之和，答案对 109+7 取模。
输入格式
第一行包含整数 n。
接下来 n 行，每行包含一个整数 ai。
输出格式
输出一个整数，表示所给正整数的乘积的约数之和，答案需对 109+7 取模。
数据范围
1≤n≤100,
1≤ai≤2×109
输入样例：
3
2
6
8
输出样例：
252
#include<bits/stdc++.h> using namespace std; const int mod=1e9+7; typedef long long LL; int main() { int n; cin>>n; map<int,int> primes; while(n--) { int x; cin>>x; for(int i=2;i<=x/i;i++) { while(x%i==0) { primes[i]++; x/=i; } } if(x>1) primes[x]++; } LL res=1; for(map<int,int>::iterator it=primes.begin();it!=primes.end();it++) { LL p=it->first,a=it->second; LL t=1; while(a--) t=(t*p+1)%mod; res=res*t%mod; } cout<<res; return 0; }
4.2.4 872. 最大公约数
给定 n 对正整数 ai,bi，请你求出每对数的最大公约数。
输入格式
第一行包含整数 n。
接下来 n 行，每行包含一个整数对 ai,bi。
输出格式
输出共 n 行，每行输出一个整数对的最大公约数。
数据范围
1≤n≤105,
1≤ai,bi≤2×109
输入样例：
2
3 6
4 6
输出样例：
3
2
#include<bits/stdc++.h> using namespace std; int gcd(int a,int b) { return b ? gcd(b,a%b) : a; } int main() { int n; cin>>n; while(n--) { int a,b; cin>>a>>b; cout<<gcd(a,b)<<endl; } return 0; }
4.3 欧拉函数
求欧拉函数 —— 模板题 AcWing 873. 欧拉函数
int phi(int x) { int res = x; for (int i = 2; i <= x / i; 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; }
筛法求欧拉函数 —— 模板题 AcWing 874. 筛法求欧拉函数
int primes[N], cnt; // primes[]存储所有素数
int euler[N]; // 存储每个数的欧拉函数
bool st[N]; // st[x]存储x是否被筛掉
void get_eulers(int n) { euler[1] = 1; for (int i = 2; i <= n; i ++ ) { if (!st[i]) { primes[cnt ++ ] = i; euler[i] = i - 1; } for (int j = 0; primes[j] <= n / i; j ++ ) { int t = primes[j] * i; st[t] = true; if (i % primes[j] == 0) { euler[t] = euler[i] * primes[j]; break; } euler[t] = euler[i] * (primes[j] - 1); } } }
4.3.1 873. 欧拉函数
给定 n 个正整数 ai，请你求出每个数的欧拉函数。
欧拉函数的定义
1∼N 中与 N 互质的数的个数被称为欧拉函数，记为 ϕ(N)。
若在算数基本定理中，N=pa11pa22…pamm，则：
ϕ(N) = N×p1−1p1×p2−1p2×…×pm−1pm
输入格式
第一行包含整数 n。
接下来 n 行，每行包含一个正整数 ai。
输出格式
输出共 n 行，每行输出一个正整数 ai 的欧拉函数。
数据范围
1≤n≤100,
1≤ai≤2×109
输入样例：
3
3
6
8
输出样例：
2
2
4
#include<bits/stdc++.h> using namespace std; int main() { int n; cin>>n; while(n--) { int x; cin>>x; int res=x; for(int i=2;i<=x/i;i++) { if(x%i==0) { res=res/i*(i-1); while(x%i==0) x/=i; } } if(x>1) res=res/x*(x-1); cout<<res<<endl; } return 0; }
4.3.2 874. 筛法求欧拉函数
给定一个正整数 n，求 1∼n 中每个数的欧拉函数之和。
输入格式
共一行，包含一个整数 n。
输出格式
共一行，包含一个整数，表示 1∼n 中每个数的欧拉函数之和。
数据范围
1≤n≤106
输入样例：
6
输出样例：
12
#include<bits/stdc++.h> using namespace std; typedef long long LL; const int N=1000010; int primes[N],cnt; int euler[N]; bool st[N]; LL get_eulers(int n) { euler[1]=1; for(int i=2;i<=n;i++) { if(!st[i]) { primes[cnt++]=i; euler[i]=i-1; } for(int j=0;primes[j]<=n/i;j++) { int t=primes[j]*i; st[t]=true; if(i%primes[j]==0) { euler[t]=euler[i]*primes[j]; break; } euler[t]=euler[i]*(primes[j]-1); } } LL res=0; for(int i=1;i<=n;i++) res+=euler[i]; return res; } int main() { int n; cin>>n; cout<<get_eulers(n); return 0; }
