https://www.cnblogs.com/linyujun/p/5198832.html
前言：好多学ACM的人都在问我数论的知识（其实我本人分不清数学和数论有什么区别，反正以后有关数学的知识我都扔进数论分类里面好了）
于是我就准备写一个长篇集，把我知道的数论知识和ACM模板都发上来（而且一旦模板有更新，我就直接在博客上改了，所以记得常来看看（。・ω・））
废话说完了，直接进入正题ヾ(=^▽^=)ノ
素数，又叫质数，定义是除了1和它本身以外不再有其他的因数
我们通过这个定义，可以写如下程序判断一个数是不是质数
1 bool prime(int x){//判断x是不是质数，是返回true，不是返回false
2 if(x <= 1) return false;
3 for(int i = 2; i < x; i ++){
4 if(x % i == 0) return false;
5 }
6 return true;
7 }
这个程序的时间复杂度是O(n)，有没有更快的方法，当然
看这个
1 bool prime(int x){//判断x是不是质数，是返回true，不是返回false
2 if(x <= 1) return false;
3 for(int i = 2; i <= sqrt(x + 0.5); i ++){//0.5是防止根号的精度误差
4 if(x % i == 0) return false;
5 }
6 return true;
7 }
8 //另一种方法，不需要根号
9 bool prime(int x){//判断x是不是质数，是返回true，不是返回false
10 if(x <= 1) return false;
11 for(int i = 2; i * i <= x; i ++){//用乘法避免根号的精度误差
12 if(x % i == 0) return false;
13 }
14 return true;
15 }
16 //根据题目不同，如果i*i会爆int，记得开longlong
这个复杂度是O(√n),速度快多了（＃°Д°）
根据题目不同，有可能你需要先预处理出1~N这N个数是否是素数
如果用刚刚的方法，复杂度就是O(n√n)
1 #include<cstdio>
2 const int N = 100000 + 5;
3 bool prime[N];
4 bool is_prime(int x){
5 if(x <= 1) return false;
6 for(int i = 2; i * i <= x; i ++){
7 if(x % i == 0) return false;
8 }
9 return true;
10 }
11 void init(){
12 for(int i = 0; i < N; i ++){
13 prime[i] = is_prime(i);
14 }
15 }
16 int main(){
17 init();
18 }
如果n大一点，就太慢了(｡･ω･)ﾉﾞ
介绍一种新方法，埃筛
埃筛--------------埃拉托斯特尼筛法，或者叫埃氏筛法
原理：如果找到一个质数，那么这个质数的倍数都不是质数
比如2是质数，那么4,6,8,10,12...都不是质数
然后看3是质数，那么6,9,12,15,18,21...都不是质数
然后看4，4已经被2标记为合数了，所以跳过
然后看5......这样一直筛下去
1 #include<cstdio>
2 const int N = 100000 + 5;
3 bool prime[N];
4 void init(){
5 for(int i = 2; i < N; i ++) prime[i] = true;//先全部初始化为质数
6 for(int i = 2; i < N; i ++){
7 if(prime[i]){//如果i是质数
8 for(int j = 2*i; j < N; j += i){//从i的两倍开始的所有倍数
9 prime[j] = false;
10 }
11 }
12 }
13 }
14 int main(){
15 init();
16 }
因为一些数字，比如6既被2的for循环经过又被3的for循环经过，所以复杂度不是O(n)
这个复杂度经过专业人士检验，复杂度O(nloglogn)（学过高数的小朋友可以自己证明≖‿≖✧当然也可以去百度）
知道原理后，我们再稍微优化一下就更快了
1 #include<cstdio>
2 const int N = 100000 + 5;
3 bool prime[N];
4 void init(){
5 for(int i = 2; i < N; i ++) prime[i] = true;
6 for(int i = 2; i*i < N; i ++){//判断改成i*i<N
7 if(prime[i]){
8 for(int j = i*i; j < N; j += i){//从i*i开始就可以了
9 prime[j] = false;
10 }
11 }
12 }
13 }
14 int main(){
15 init();
16 }
好戏都是要留到最后的≖‿≖✧确实还有O(n)的做法
这个算法名字叫线筛
1 #include<cstdio>
2 const int N = 100000 + 5;
3 bool prime[N];//prime[i]表示i是不是质数
4 int p[N], tot;//p[N]用来存质数
5 void init(){
6 for(int i = 2; i < N; i ++) prime[i] = true;//初始化为质数
7 for(int i = 2; i < N; i++){
8 if(prime[i]) p[tot ++] = i;//把质数存起来
9 for(int j = 0; j < tot && i * p[j] < N; j++){
10 prime[i * p[j]] = false;
11 if(i % p[j] == 0) break;//保证每个合数被它最小的质因数筛去
12 }
13 }
14 }
15 int main(){
16 init();
17 }
这个方法可以保证每个合数都被它最小的质因数筛去
所以一个数只会经过一次
时间复杂度为O(n)
其实loglogn非常小，把埃筛看成线性也无妨，毕竟它比线筛好写
基于埃筛的原理，我们可以用它干很多事
比如预处理每个数的所有质因数
#include<cstdio>
#include<vector>
using namespace std;
const int N = + ;
vector<int > prime_factor[N];
void init(){
for(int i = ; i < N; i ++){
if(prime_factor[i].size() == ){//如果i是质数
for(int j = i; j < N; j += i){
prime_factor[j].push_back(i);
}
}
}
}
int main(){
init();
}
比如预处理每个数的所有因数
#include<cstdio>
#include<vector>
using namespace std;
const int N = + ;
vector<int > factor[N];
void init(){
for(int i = ; i < N; i ++){
for(int j = i; j < N; j += i){
factor[j].push_back(i);
}
}
}
int main(){
init();
}
比如预处理每个数的质因数分解
#include<cstdio>
#include<vector>
using namespace std;
const int N = + ;
vector<int > prime_factor[N];
void init(){
int temp;
for(int i = ; i < N; i ++){
if(prime_factor[i].size() == ){
for(int j = i; j < N; j += i){
temp = j;
while(temp % i == ){
prime_factor[j].push_back(i);
temp /= i;
}
}
}
}
}
int main(){
init();
}
https://vjudge.net/contest/240113#problem/A
https://vjudge.net/contest/240113#problem/H
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxm = 1e6 + ;
bool is_prime[maxm];
bool is_prime_small[maxm];
//对区间【a, b)内的整数执行筛选。is_prime[i - a] = true i是素数
void segment_solve(ll a, ll b) {
for(int i = ; (ll) i * i < b; i++) is_prime_small[i] = true;
for(int i = ; i < b - a; i++) is_prime[i] = true;
for(int i = ; (ll) i * i < b; i++) {
if(is_prime_small[i]) {
for(int j = * i; (ll) j * j < b; j += i) is_prime_small[j] = false;//筛[2, 根号b)
for(ll j = max(2LL, (a + i - ) / i) * i; j < b; j += i) is_prime[j - a] = false;//筛[a, b)
}
}
}
int main() {
segment_solve(20LL, 100LL);
for(int i = ; i < ; i++) {
if(is_prime[i] == true) printf("%d\n", i + );
}
return ;
} 这个是求区间素数的代码。挑战书上
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long LL;
const int N=1e5+; bool vis[N],visab[N];
int prime[N],cnt=;
void is_prime()
{
memset(vis,,sizeof(vis));
vis[]=;
for(int i=;i<N;i++)
{
if(!vis[i])
{
prime[cnt++]=i;
for(int j=i+i;j<N;j+=i)
vis[j]=;
}
}
} int main()
{
int t;
cin>>t;
is_prime();
for(int kase=;kase<=t;kase++)
{
LL a,b;
scanf("%lld%lld",&a,&b);
int count=;
if(b<=N-)
{
for(LL i=a;i<=b;i++)
{
if(!vis[i])
count++;
}
}
else
{
memset(visab,,sizeof(visab));
for(int i=;i<cnt&&prime[i] * prime[i]<=b;i++)
{
LL k=a/prime[i];
if(k*prime[i]<a)
k++;
for(LL j=k*prime[i];j<=b;j+=prime[i])
{
visab[j-a]=;
}
}
for(LL i=a;i<=b;i++)
{
if(!visab[i-a])
count++;
}
}
printf("Case %d: %d\n",kase,count);
}
}
题目：给定整数a和b;请问区间【a, b)内有多少个素数
a < b <= 1e12;
b - a <= 1e6;
先分别做好2到根号b的表和a到b 的表，然后从2到根号b的表筛的素数的同时，也将其倍数从a到b的表中划去，最后剩下的就是a到b的素数了。
https://vjudge.net/contest/230809#problem/T
给定一个七位数，然后他的反转数是一个素数，且要小于1e6，说明原七位数最后一位为零。
题目要求满足这些条件的七位数的质因子之和，然后还有可能删除某个数。
所以用两个树状数组，一个记录个数，一个记录值。
#include<bits/stdc++.h> using namespace std;
typedef long long ll;
const int maxm = 1e6 + ;
int pri[maxm], is_p[maxm], a[maxm];
int num[];
ll bit_a[maxm], bit_b[maxm];
ll fac[maxm];
map<int, int> mapp;
int cnt;
ll cal(int x) {
int ax = x;
int c = ;
while(ax) {
num[c++] = ax % ;
ax /= ;
}
ll res = ;
for(int i = ; i < c; i++) {
res = res * + num[i];
}
while(res < 1e5) res *= ;
return res;
}
void init() {
cnt = ;
for(int i = ; i < 1e6; i++) is_p[i] = ;
for(int i = ; i < 1e6; i++) {
if(is_p[i]) {
pri[++cnt] = i;
for(int j = * i; j < 1e6; j += i) {
is_p[j] = ;
}
}
}
for(int i = ; i <= cnt; i++) {
a[i] = cal(pri[i]);
}
sort(a + , a + cnt + );
for(int i = ; i <= cnt; i++) {
mapp[a[i] ] = i;
}
for(int i = ; i <= cnt; i++) {
int tmp = a[i];
fac[i] = ;
for(int j = ; j <= cnt && pri[j] * pri[j] <= tmp; j++) {
while(tmp % pri[j] == ) {
tmp /= pri[j];
fac[i]++;
}
} if(tmp > ) fac[i]++;
}
} int lowbit(int x) {
return x & -x;
} void add(int x, ll val, ll bit[]) {
while(x <= cnt) {
bit[x] += val;
x += lowbit(x);
}
} ll sum(int x, ll bit[]) {
ll s = ;
while(x > ) {
s += bit[x];
x -= lowbit(x);
}
return s;
} char ch[];
int x;
int main() {
init();
memset(bit_a, , sizeof(bit_a));
memset(bit_b, , sizeof(bit_b));
for(int i = ; i <= cnt; i++) {
add(i, , bit_a);
add(i, fac[i], bit_b);
}
while(~scanf("%s", ch)) {
scanf("%d", &x);
if(ch[] == 'q') {
x++;
int l = , r = cnt, mid, res = cnt + ;
while(l <= r) {
mid = (l + r) >> ;
if(sum(mid, bit_a) >= x) {
res = mid;
r = mid - ;
}
else {
l = mid + ;
}
}
printf("%lld\n", sum(res, bit_b));
}
else if(ch[] == 'd') {
int pos = mapp[x / ];
add(pos, -, bit_a);
add(pos, -fac[pos], bit_b);
}
}
return ;
}
求解C(2*n,n)/(n+1);
即(2*n)!/(n+1)!/n!。
用欧拉筛法，O（n）的效率求出每个质数。然后枚举阶乘，像质数表一样把一个数给分解。但是效率很低。
【优化1】如果一个数是合数，我们可以把它的某个因子记下来。然后我们同样从开始枚举阶乘，而且是倒着枚举。对于每个数，如果它是合数，我就把它分解。比如，设f[n]为结果中含有n因子的个数。u是n的一个约数。那么我们可以f[u]+=f[n],f[n/u]+=f[n]。这样就不用多次用快速幂了。直到n是质数为止。
【优化2】开始可以把1–n的f[i]设为-1，把n+2–2*n(注意，最后要除n+1,所以从n+2开始)的f[i]设为1.这样只需1次循环。
#include<cstdio>
using namespace std;
typedef long long ll;
ll prime[],a[],come[];
ll temp,n,p,i,j,cnt,mod;
ll pow(ll a,ll b)
{
ll ans;
for (ans=;b;b=b/,a=a*a%mod)
if (b&) ans=ans*a%mod;
return ans;
}
int main()
{
scanf("%lld%lld",&n,&mod);
for (i=;i<=n*;i++)
{
if (!come[i]) prime[++cnt]=i;
for (j=;j<=cnt&&prime[j]*i<=n*;j++)
come[prime[j]*i]=i;
}
temp=;
for (i=;i<=n;i++) a[i]=-;
for (i=n+;i<=*n;i++) a[i]=;
for (i=n*;i>;i--)
if (come[i])
{
a[come[i]]+=a[i];
a[i/come[i]]+=a[i];
}
else
temp=temp*pow(i,a[i])%mod; printf("%lld",temp);
return ;
}