简单数论入门和基础数学知识（未完）
????????因?yàn)橐郧皬膩頉]接觸過數(shù)論，小學(xué)也沒搞過奧數(shù)，而且數(shù)論這東西又挺重要的，不只是比賽，有些東西基本算是常識(shí)需要知道的。而且內(nèi)容還很雜。所以決定好好寫一篇博客，包括知識(shí)點(diǎn)和自己的理解。
目錄
0.特殊性質(zhì)
一.分解質(zhì)因數(shù)和算術(shù)基本定理
如何分解質(zhì)因數(shù)
二.判斷素?cái)?shù) 和素?cái)?shù)篩（埃篩和歐拉篩）
素?cái)?shù)判斷
素?cái)?shù)篩法
三.約數(shù)
一個(gè)數(shù)的所有約數(shù)
約數(shù)個(gè)數(shù)?
約數(shù)之和
最大公約數(shù)GCD
四.歐拉函數(shù)和歐拉函數(shù)篩及歐拉定理
求一個(gè)數(shù)的歐拉函數(shù)
歐拉函數(shù)篩
歐拉定理
費(fèi)馬小定理
0.特殊性質(zhì)
平常寫題會(huì)碰到的一些特殊性質(zhì)。
整除性質(zhì)：
1、若b|a，c|a，且b和c互質(zhì)，則bc|a。
2、對(duì)任意非零整數(shù)a，±a|a=±1。
3、若a|b，b|a，則|a|=|b|。
4、如果a能被b整除，c是任意整數(shù)，那么積ac也能被b整除。
5、如果a同時(shí)被b與c整除，并且b與c互質(zhì)，那么a一定能被積bc整除，反過來也成立。
6、對(duì)任意整數(shù)a，b>0，存在唯一的數(shù)對(duì)q，r，使a=bq+r，其中0≤r<b，這個(gè)事實(shí)稱為帶余除法定理，是整除理論的基礎(chǔ)。
7、公因數(shù)一定整除最大公因數(shù)。
8.d|a,d|b 則d|ax+by。
9.整除的傳遞性。若a|b b|c 則a|c。
1.定理：兩數(shù)最大公約數(shù)與最小公倍數(shù)的積等于兩數(shù)之積?
所以互質(zhì)的兩數(shù)乘積就是最小公倍數(shù)。
2.
一.分解質(zhì)因數(shù)和算術(shù)基本定理
? ? ? ?① 惟一分解定理 (算術(shù)基本定理)?可表述為：任何一個(gè)大于1的自然數(shù)?N,如果N不為質(zhì)數(shù)，那么N可以唯一分解成有限個(gè)質(zhì)數(shù)的乘積N=，這里P1<P2<P3......<Pn均為質(zhì)數(shù)，其中指數(shù)ai是正整數(shù)。這樣的分解稱為?N?的標(biāo)準(zhǔn)分解式。
? ? ? ? ②質(zhì)因數(shù)（素因數(shù)或質(zhì)因子）在數(shù)論里是指能整除給定正整數(shù)的質(zhì)數(shù)。除了1以外，兩個(gè)沒有其他共同質(zhì)因子的正整數(shù)稱為互質(zhì)。因?yàn)?沒有質(zhì)因子，1與任何正整數(shù)（包括1本身）都是互質(zhì)。正整數(shù)的因數(shù)分解可將正整數(shù)表示為一連串的質(zhì)因子相乘，質(zhì)因子如重復(fù)可以用指數(shù)表示。根據(jù)算術(shù)基本定理，任何正整數(shù)皆有獨(dú)一無二的質(zhì)因子分解式??。只有一個(gè)質(zhì)因子的正整數(shù)為質(zhì)數(shù)。
如何分解質(zhì)因數(shù)
分解質(zhì)因數(shù)，也就是將n表示為標(biāo)準(zhǔn)分解式。所以我們要求出質(zhì)因數(shù)和對(duì)應(yīng)的指數(shù)。
試除法：
為什么只要枚舉到sqrt(n)就行呢？
因?yàn)槌^sqrt(n)的部分基本沒有意義，因?yàn)槿绻嬖诙鄠€(gè)大于sqrt(n)的質(zhì)因數(shù)，根據(jù)惟一分解定理，n由這些數(shù)相乘組成，那么多個(gè)大于sqrt(n)的質(zhì)因數(shù)相乘就超過了n，矛盾。
所以最多只會(huì)有一個(gè)大于sqrt(n)的質(zhì)因數(shù)，所以當(dāng)枚舉到sqrt(n)時(shí)剩下的數(shù)不等于1，那么說明還剩下這個(gè)大于sqrt(n)的質(zhì)因數(shù)。額外加上即可。
vector<pair<int,int>> div(int n){vector<pair<int,int>> ans; //因?yàn)槲┮环纸舛ɡ?#xff0c;合數(shù)也是由多個(gè)質(zhì)數(shù)組成，合因數(shù)組成的較小質(zhì)數(shù)會(huì)被先分解，所以每次得到的必定是質(zhì)因數(shù)for(int j=2;j<=n/j;j++){//除凈小于sqrt(n)的質(zhì)因數(shù)int sum=0;while(n%j==0){//除凈質(zhì)因數(shù)n/=j;sum++;//該質(zhì)因數(shù)的指數(shù)}if(sum!=0)ans.push_back({j,sum});}if(n>1)//大于sqrt(n)的質(zhì)因數(shù)只會(huì)有一個(gè)，如果有多個(gè)，分解定理的乘積就大于n了ans.push_back({n,1});return ans; }unordered_map<int,int> div(int n){//得到質(zhì)因數(shù)unordered_map<int,int>ans;for(int j=2;j<=n/j;j++){if(n%j==0){while(n%j==0){n/=j;ans[j]++;} }}if(n>1)ans[n]++;return ans; }參考：
數(shù)學(xué)數(shù)論相關(guān) - ternary_tree 的博客 - 洛谷博客 (luogu.org)
二.判斷素?cái)?shù) 和素?cái)?shù)篩（埃篩和歐拉篩）
素?cái)?shù)判斷
·????????根據(jù)素?cái)?shù)的定義，只含有1和本身的因數(shù)的數(shù)被稱為素?cái)?shù)，由此定義枚舉小于這個(gè)數(shù)的所有數(shù)，如果出現(xiàn)能夠整除的，說明這個(gè)數(shù)不是質(zhì)數(shù)。
注意：此處只需要枚舉到sqrt(k)。
因?yàn)?若 i | k，則 k/i | k
所以i如果不是因數(shù)，那么k/i也不是，最多到sqrt(k)，超過這個(gè)范圍就沒有意義了。
O(sqrt(n))
此處兩數(shù)相乘采用逆元，可以防止爆int
int is_prime(int k) {//判斷k是否是質(zhì)數(shù)int ok = 1;if (k < 2)return 0;for (int j = 2; j <= k / j; j++) {//枚舉到sqrt(k)if (k % j == 0) {ok = 0;return 0;}}return 1; }?素?cái)?shù)篩法
P3383 【模板】線性篩素?cái)?shù) - 洛谷 | 計(jì)算機(jī)科學(xué)教育新生態(tài) (luogu.com.cn)
? ? ? ? 1.埃篩的思想比較簡(jiǎn)單，一個(gè)數(shù)的所有倍數(shù)都不可能是質(zhì)數(shù)所以，枚舉當(dāng)前數(shù)的范圍內(nèi)所有倍數(shù)，將他們刪去，剩下的都是質(zhì)數(shù)。同時(shí)可以簡(jiǎn)單優(yōu)化一下，由惟一分解定理，只需要篩去質(zhì)數(shù)，合數(shù)也就會(huì)被順帶篩去。所以枚舉質(zhì)數(shù)的倍數(shù)即可。優(yōu)化后復(fù)雜度O(nloglog)
? ? ? ? 2.歐拉篩也叫做線性篩。他保證每次篩的時(shí)候只會(huì)通過一個(gè)質(zhì)因數(shù)將一個(gè)合數(shù)篩去，而不像埃篩那樣重復(fù)篩同一個(gè)數(shù)好多次。
其主要的優(yōu)化有兩方面：
①每次只枚舉質(zhì)數(shù)的倍數(shù)。
②保證prime[i]是某個(gè)被篩去的合數(shù)的最小質(zhì)因數(shù).
重點(diǎn)在第二點(diǎn)。因?yàn)槲覀兪菑男〉酱竺杜e的質(zhì)數(shù)，那么當(dāng)?shù)谝淮螡M足判斷的數(shù)j,j%prime[i]==0那么這個(gè)prime[i]就是j的最小質(zhì)因數(shù)，同時(shí)也是prime[i]*j的最小質(zhì)因數(shù)。同時(shí)，因?yàn)閜rime[i]是j的最小質(zhì)因數(shù)，那么prime[i]也會(huì)是之后prime[i+1~size]*j這些合數(shù)的最小質(zhì)因數(shù)。
原理：歐拉篩篩素?cái)?shù) - 學(xué)委 的博客 - 洛谷博客 (luogu.com.cn)
#include<bits/stdc++.h> using namespace std; #pragma warning(disable:4996); //#define int long long #define rep(j,b,e) for(int j=(b);j<=(e);j++) #define drep(j,e,b) for(int j=(e);j>=(b);j--) const int N = 1e8 + 10; int T = 1; int n, m, k; int gcd(int a, int b) {return a % b == 0 ? b : gcd(b, a % b); } vector<int>prime; int NotisPrime[N];//1表示不是一個(gè)質(zhì)數(shù) void GetPrime_Era(int n) {//會(huì)多次標(biāo)記同一個(gè)值rep(j, 2, n) {if (NotisPrime[j] == 0) {//如果是質(zhì)數(shù)prime.push_back(j);for (int i = j; i <= n/j; i++)//質(zhì)數(shù)的倍數(shù)全是合數(shù),逆元寫成/j防止爆intNotisPrime[i * j] = 1;}} } void GetPrime_Ola(int n) {//效率更高，一個(gè)數(shù)只會(huì)被他的最小質(zhì)因數(shù)篩掉rep(j, 2, n) {if (NotisPrime[j] == 0)//篩完還是素?cái)?shù)就加入prime.push_back(j);for (int i = 0; i < prime.size() && prime[i] <= n/j; i++) {//逆元枚舉質(zhì)數(shù)，篩pi*jNotisPrime[j * prime[i]] = 1;if (j % prime[i] == 0)break;//保證prime[i]是這個(gè)合數(shù)的最小質(zhì)因數(shù)}} } signed main() { #ifndef ONLINE_JUDGEfreopen("out.txt", "w", stdout); #endifios::sync_with_stdio(0); cout.tie(0);int q;cin >> n >> q;GetPrime_Ola(n);rep(j, 1, q) {cin >> k;cout << prime[k - 1] << endl;} }三.約數(shù)和公約數(shù)
一個(gè)數(shù)的所有約數(shù)
試除法
枚舉到sqrt(n) ，原理同判斷質(zhì)數(shù)。
vector<int> div(int k){vector<int>ans;for(int j=1;j<=k/j;j++){if(k%j==0){ans.push_back(j);if(j!=k/j)ans.push_back(k/j);}}sort(ans.begin(),ans.end());//k的約數(shù)約有l(wèi)og個(gè)return ans; }約數(shù)個(gè)數(shù)?
870. 約數(shù)個(gè)數(shù) - AcWing題庫
本題是求一個(gè)很大乘積的約數(shù)，而這個(gè)很大的數(shù)不比表示出來，他的標(biāo)準(zhǔn)分解式就等于每個(gè)乘數(shù)的標(biāo)準(zhǔn)分解式的乘積。
由算術(shù)基本定理：
N=
一個(gè)數(shù)的約數(shù)個(gè)數(shù) sum=?,也就是質(zhì)因數(shù)指數(shù)+1的乘積。
因?yàn)樗阈g(shù)基本定理，里面的質(zhì)因數(shù)隨意組合得到的數(shù)都是N的約數(shù)，每個(gè)質(zhì)因數(shù)有0-ai種選法，由乘法原理，總的選擇數(shù)為指數(shù)+1的乘積。
做法：
先對(duì)數(shù)N進(jìn)行質(zhì)因數(shù)分解，求出質(zhì)因數(shù)和對(duì)應(yīng)指數(shù)，然后求指數(shù)+1的乘積即可。
#include<bits/stdc++.h> using namespace std; const int mod=1e9 +7; int main(){int n;cin>>n;unordered_map<int,int>prime;//質(zhì)因數(shù)和指數(shù)while(n--){int k;cin>>k;for(int j=2;j<=k/j;j++){//分解質(zhì)因數(shù)得到底數(shù)和指數(shù)while(k%j==0){k/=j;prime[j]++;}}if(k>1)prime[k]++;}long long ans=1;for(auto [p,cnt]:prime){ans=(ans*(cnt+1))%mod;//約數(shù)個(gè)數(shù)等于分解式的所有指數(shù)+1的乘積}cout<<ans<<endl; }約數(shù)之和
871. 約數(shù)之和 - AcWing題庫
根約數(shù)個(gè)數(shù)的推導(dǎo)類似，所有質(zhì)因數(shù)及其指數(shù)的排列組合構(gòu)成所有的因數(shù)，所以約數(shù)和就是將每種組合都列出來然后相加，而提取公因式后可以得到
sum=
也就是所有質(zhì)因數(shù)的所有指數(shù)的和的乘積
所以做法和約數(shù)個(gè)數(shù)很像，先分解質(zhì)因數(shù)求出質(zhì)因數(shù)和指數(shù)，然后寫出公式。
這里求一個(gè)質(zhì)因數(shù)的所有指數(shù)的和有個(gè)簡(jiǎn)便方法。
迭代 t=p*t+1
#include<bits/stdc++.h> using namespace std; const int mod=1e9 +7; int main(){int n;cin>>n;unordered_map<int,int>prime;//質(zhì)因數(shù)和指數(shù)while(n--){int k;cin>>k;for(int j=2;j<=k/j;j++){//分解質(zhì)因數(shù)得到底數(shù)和指數(shù)while(k%j==0){k/=j;prime[j]++;}}if(k>1)prime[k]++;}long long ans=1;for(auto [p,cnt]:prime){long long t=1;while(cnt--)t=(p*t+1)%mod;//質(zhì)因數(shù)所有指數(shù)的和ans=(ans*t)%mod;//求積}cout<<ans<<endl; }最大公約數(shù)GCD
輾轉(zhuǎn)相除法：
如果
?且??則有
所以對(duì)于A和B的最大公約數(shù)，則會(huì)滿足? ?用取模加快減法運(yùn)算
得到
int gcd(int a,int b){return b==0?a:gcd(b,a%b); }?裴蜀定理
設(shè)??是不全為零的整數(shù)，則存在整數(shù)?, 使得?.
且gcd(a,b)是能得到的最小值，其他值全是gcd的倍數(shù)。
擴(kuò)展歐幾里得算法
877. 擴(kuò)展歐幾里得算法 - AcWing題庫
擴(kuò)展歐幾里得算法是用來求解裴蜀定理中的x和y的。
好煩不會(huì)證明qwq
#include <iostream> #include <cstring> #include <algorithm>using namespace std; //a*b+b*y=gdc(a,b) int exgcd(int a,int b,int& x,int& y){if(b==0){x=1,y=0;return a;}int res=exgcd(b,a%b,y,x);y-=a/b*x;return res; } int main() {int n;cin>>n;while (n -- ){int a,b,x,y;cin>>a>>b;exgcd(a,b,x,y);cout<<x<<" "<<y<<endl;} }?線性同余方程
878. 線性同余方程 - AcWing題庫
線性同余方程：
得
由擴(kuò)展歐幾里得，可得
的x，
又因?yàn)間cd(a,p) | (ax+by)
所以，如果b是gcd(a,p)的倍數(shù)，方程有解且解為方程的倍，反之無解。
所以先用gcd判斷有解后，使用擴(kuò)展歐幾里得算法得到，然后擴(kuò)大倍即可
#include <iostream> #include <cstring> #include <algorithm> using namespace std; typedef long long LL;int n; int a,b,p; int exgcd(int a,int b,int &x,int &y){if(b==0)//mod等于0相當(dāng)于整除{//a*1+b*0=ax=1,y=0;return a;}int d=exgcd(b,a%b,y,x);y-=a/b*x;return d; } int main() {cin >> n;while (n -- ){cin>>a>>b>>p;int x,y;int d=exgcd(a,p,x,y);//a*x=p*y+bif(b%d)cout<<"impossible"<<endl;else{x=(LL)x*(b/d)%p;cout<<x<<endl;}} }四.歐拉函數(shù)和歐拉函數(shù)篩及歐拉定理
求一個(gè)數(shù)的歐拉函數(shù)
873. 歐拉函數(shù) - AcWing題庫
?與N互質(zhì)的數(shù)的個(gè)數(shù)稱為N的歐拉函數(shù)，記做phi[N]
歐拉函數(shù)值可以通過上表的公式得到，可以看到N的歐拉函數(shù)只與質(zhì)因數(shù)有關(guān)，和指數(shù)無關(guān)。
證明依靠容斥定理，略。
可以做法就是先求出N的所有質(zhì)因數(shù)，然后帶入公式
#include <iostream> #include <cstring> #include <algorithm> using namespace std; unordered_map<int,int> div(int n){//得到質(zhì)因數(shù)unordered_map<int,int>ans;for(int j=2;j<=n/j;j++)if(n%j==0)while(n%j==0){n/=j;ans[j]++;} if(n>1)ans[n]++;// 惟一一個(gè)大于sqrt(n) 的質(zhì)因數(shù)不要遺漏return ans; } int main() {int n;cin >> n;while (n -- ){int k;cin >> k;auto ans=div(k);int res=k;for(auto&[prime,cnt]:ans){res=res/prime*(prime-1);//帶入公式，注意都是整除。可以先除prime，因?yàn)閜rime是質(zhì)因數(shù)，N能正常prime，然后再乘prime-1保證精度不丟失}cout<<res<<endl;} }歐拉函數(shù)篩
874. 篩法求歐拉函數(shù) - AcWing題庫
可以根據(jù)線性篩的思路，得到質(zhì)數(shù)，根據(jù)質(zhì)數(shù)作為某個(gè)數(shù)的質(zhì)因數(shù)進(jìn)行篩。
根據(jù)公式可以推出，
①j為質(zhì)數(shù)數(shù)，歐拉函數(shù)ola[j]=j-1，因?yàn)橘|(zhì)數(shù)的質(zhì)因子只有他本身，也可以認(rèn)為質(zhì)數(shù)之前的所有數(shù)都和他自己互質(zhì)（公約數(shù)只為1）
②pi為質(zhì)數(shù)，j為任意數(shù),且pi是j的質(zhì)因子
根據(jù)歐拉公式，pi*j和 j 的質(zhì)因數(shù)無差別，只有pi的指數(shù)有差別歐拉函數(shù)和質(zhì)因子指數(shù)無關(guān)，所有歐拉函數(shù)的差別僅在N上。
易得 ola[pi*j]=pi*ola[j]
③pi為質(zhì)數(shù)，j為任意數(shù)，且pi不是j的質(zhì)因子
根據(jù)歐拉公式，pi*j和j的標(biāo)準(zhǔn)分解式差距只在pi*j多一個(gè)pi。帶入歐拉公式
多一個(gè)pi*(pi-1)/pi=pi-1
易得 ola[pi*j]=(pi-1)*ola[j]
#include <bits/stdc++.h>using namespace std; int n; const int N = 1e6+10; vector<int>prime; int NotIsPrime[N]; long long ola[N]; long long get_ola(int n){ola[1]=1;//1的歐拉函數(shù)為1for(int j=2;j<=n;j++){if(NotIsPrime[j]==0){prime.push_back(j);ola[j]=j-1;//質(zhì)數(shù)前面的所有數(shù)都與他互質(zhì)}for(int i=0;i<(int)prime.size() and prime[i]<=n/j;i++){NotIsPrime[prime[i]*j]=1;if(j%prime[i]==0){ola[j*prime[i]]=prime[i]*ola[j];//pi是j的最小質(zhì)因數(shù)，歐拉函數(shù)和質(zhì)因數(shù)指數(shù)無關(guān)，大小只變化pi倍break;}else{ola[j*prime[i]]=ola[j]*(prime[i]-1);;//*prime[i]-1;//根據(jù)歐拉函數(shù)公式，乘上非質(zhì)因數(shù)之后變化pi*((pi-1)/pi),也就是pi-1倍}}}return accumulate(ola,ola+n+1,0ll); } int main() {cin>>n;cout<<get_ola(n); }歐拉定理
若 a和b互質(zhì)，則?
證明：
設(shè)為與b互質(zhì)的數(shù)的集合。
給集合每個(gè)數(shù)乘上一個(gè)a得到集合
，集合元素相乘，提取a，同時(shí)mod b
消去相同部分
費(fèi)馬小定理
由歐拉定理，當(dāng)b為質(zhì)數(shù)時(shí)phi[b]=b-1
五.快速冪
快速冪的本質(zhì)思路還是倍增，將冪表示為二進(jìn)制即用二進(jìn)制表示所有數(shù)。
例如3^5，5的二進(jìn)制 101，可以看作2^0+2^2所以原式可以寫成?
所以用一個(gè)數(shù)存儲(chǔ),到當(dāng)前位是2的幾次方，如果該位為1，說明需要乘上。
注意快速冪防止爆int須先轉(zhuǎn)為long long在進(jìn)行運(yùn)算，不能運(yùn)算完再強(qiáng)轉(zhuǎn)
int qpow(int a,int n){int ans=1;while(n){if(n&1==1)ans=((ll)ans*a)%mod;//當(dāng)前位為1n>>=1;//移位a=((ll)a*a)%mod;//當(dāng)前位是2的幾次方}return ans%mod; }?快速冪求逆元
876. 快速冪求逆元 - AcWing題庫
也就是b與p互質(zhì)（gcd(b,p)==1且保證同余p結(jié)果相同的情況下，用a乘上x表示a/b。x就叫b的逆元?。
由
將
兩邊同乘b，除a
得
?由費(fèi)馬小定理，如果p為質(zhì)數(shù)時(shí)
所以b與p互質(zhì)且p為質(zhì)數(shù)時(shí)逆元x=
又因?yàn)閜為質(zhì)數(shù)，b要與p互質(zhì)只需要b不是p的整數(shù)倍即可。
所以p為質(zhì)數(shù)時(shí)求b的逆元等效于求
使用快速冪
#include<bits/stdc++.h> using namespace std; int n; int a,p; #define ll long long ll qpow(int a,int b){ll ans=1;while(b){if(b&1)ans=(ll)ans*a%p;b>>=1;a=(ll)a*a%p;}return ans%p; } int gcd(int a,int b){return b==0?a:gcd(b,a%b); } int main(){cin>>n;while(n--){cin>>a>>p;int res=qpow(a,p-2);if(a%p!=0){//（gcd(a,p)==1.p為質(zhì)數(shù)，其他數(shù)若與他互質(zhì)，只能不是p的整數(shù)倍cout<<res<<endl;}elsecout<<"impossible\n";} }總結(jié)
以上是生活随笔為你收集整理的简单数论入门和基础数学知识（未完）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 【MapGIS精品教程】005：MapG
- 下一篇： 蒙特卡洛模拟 matlab实例,蒙特卡洛