数论知识点总结(一)

文章目录

目录

文章目录

前言

一、数论有哪些

二、题法混讲

1.素数判断,质数,筛法

2.最大公约数和最小公倍数

3.快速幂

4.约数

---

前言

现在针对CSP-J/S组的第一题主要都是数论,换句话说,持数论之剑,可行天下矣!

---

一、数论有哪些

数论 原根,素数判断,质数,筛法最大公约数,gcd扩展欧几里德算法,快速幂,exgcd,不定方程,进制,中国剩余定理,CRT,莫比乌斯反演,逆元,Lucas 定理,类欧几里得算法,调和级数,欧拉降幂......

但是,可但是,但可是,我是个蒟蒻,只能胜任很简单的数论和算法,今天只是做个考前复习罢了

二、题法混讲

1.素数判断,质数,筛法

(1)素数,质数的定义:只能被一和他本身整除的正整数教素数,又称质数(2是素数,0和1却不是)

(2)判定

代码如下（示例）：

bool isprime(int n){if(n<2) return false;int x=sqrt(n);for(int i=2;i<=x;i++)if(n%i==0) return false;return true;
}

(3)埃氏筛

代码如下（示例）：

void get_primes(int n){for(int i=2;i<=n;i++){if(!flag[i]){p[++cnt]=i; for(int j=1;p[j]<=n/i;j++){flag[p[j]*i]=true;}}}
}

(4)线性筛

代码如下（示例）：

void get_primes(int n){for(int i=2;i<=n;i++){if(!flag[i]){p[++cnt]=i;for(int j=1;p[j]<=n/i;j++){flag[p[j]*i]=true;if(i%p[j]==0) break;}}}
}

2.最大公约数和最小公倍数

代码如下（示例）：

int gcd(int x,int y){if(y==0) return x;return gcd(y,x%y);
}
int lcm(int x,int y){return x*y/gcd(x,y);
}

3.快速幂

递归写法:

int ksm(int a,int b,int mod){if(!b) return 1;int t=ksm(a,b>>1,mod);return (LL)(b&1?a:1)*t%mod*t%mod;
}

非递归写法:

①
int ksm(int a,int b,int mod){int res=1;while(b){if(b&1) res=(LL)res*a%mod;a=a*a%mod;b>>=1;}return res;
}
②
int ksm(int a,int b,int mod){int ans=1;for(;b;a*=a,a%=mod,b>>=1)if(b&1) ans*=a,ans%=mod;return ans;
}

4.约数

代码如下(实例):

vector<int> d;
void solve(int n){d.clear();for(int i = 1; i <= n / i; i ++){if(n % i == 0){d.push_back(i);if(i != n / i) d.push_back(n / i);}}sort(d.begin(), d.end());for(auto x : d) cout << x << " ";
}

---

祝大家CSP-J/S,RP++