一些知識

整除

自然數(shù)a可以被自然數(shù)b整除或者說b是a的約數(shù)表示的是：
$a\%b=0$，即a是b的倍數(shù)，b是a的約數(shù)（不要弄反了），記作b|a。
（0是自然數(shù)也是整數(shù)）

質數(shù)（素數(shù)）和合數(shù)

指在大于1的自然數(shù)中，除了1和它本身不再有其他因數(shù)的自然數(shù)（如：2，3，5）；一個大于1的整數(shù)，如果除了1和它本身以外，還有其他的約數(shù)，這樣的數(shù)就叫作合數(shù)。

素數(shù)的分布

目前素數(shù)的分布還不能確定，但是能夠給出一個近似分布，$\pi (n)$為不超過n的質數(shù)的個數(shù)，$$\pi (n)～\frac{n}{lnn}$$
證明灰常的復雜，感興趣的可以看這里

質因數(shù)

對于給定的自然數(shù)n，x是其質因數(shù)，當且x是n的因數(shù)且x是質數(shù)。

最大公因數(shù)

記作gcd（）。

最小公倍數(shù)

記作lcm（）。

互質

如果兩個或兩個以上的整數(shù)的最大公約數(shù)為1，則他們互質，記作$a\perp b$

唯一分解定理

任何一個大于1的數(shù)都可以被分解為有限個質數(shù)乘積的形式，并且分解方式是唯一的，
質數(shù)是一個整數(shù)最基本的特征，很多問題都從質數(shù)的角度考慮
如：300=22355 12=223
一個結論：
若$a=q_1^{n_1}{q}_2^{n_2}$，且b|a，則$b=q_1^{b_1}{q}_2^{b_2}$，且$b_i大于等于0，小于與等于n_i$
對于下圖中的約束，對應約束個數(shù)：
（來源參考）

約束個數(shù)中加一是考慮了還有1

完全平方數(shù)

若一個數(shù)能表示成某個整數(shù)的平方的形式，則稱這個數(shù)為完全平方數(shù)。

例題

求解兩個數(shù)最大公因數(shù)

如果暴力求解的話，即從一開始遍歷，復雜度為$O(mina,b)$；而歐幾里得算法（輾轉相除法復雜度可化簡為$O(logn)$）

定理

gcd(a,b)=gcd(b,r)，其中r為a/b的余數(shù)
嚴格的邏輯證明這里省略，簡單的說下思路：
假設gcd(a,b)=c， 那么假設$a=k_{1}c,b=k_{2}c$,$a/b=k\dots r$,則$r=a?bk=k_{1}c?b{k}_{2}c=(k_1?b{k}_2)c$,即可以得到r也是c的倍數(shù)，還要說明c是r和b的最大公因數(shù)，
現(xiàn)在$b=k_{2}c$,$r=(k_1?b{k}_2)c$,需要證明$k_2和(k_1?b{k}_2)$互質，可以用反證法，如果不互質的話，會存在一個比c大的公因數(shù)，矛盾，所以不成立。

代碼

int gcd(int a,int b) {return b==0? a:gcd(b,a%b); } //b=0的時候，假如gcd（6，3），那么下一步遞歸得到gcd(3,0)即為3

補充性質

$$gcd（ka,kb）=kgcd(a,b)$$
$$lcm(a,b)=\frac{a?b}{gcd(a,b)}$$

素數(shù)判定

枚舉是否含有除了1和本身的因數(shù)，其實只用枚舉$2?\sqrt{n}$就行，因為如果不是素數(shù)，那么必存在$n=ab$,用反證法可以證明必有一個數(shù)小于$\sqrt{n}$;

代碼

bool is_prime(int n) {if(x<=1)return false;for(int i=2;i*i<=n;i++){if(x%i!=0)return true;}return false; }

多個素數(shù)判定

假如給你1-n，n個數(shù)，讓你判斷這n個數(shù)是不是素數(shù)，如果按照上述算法每個判斷的話，復雜度為$O(n\sqrt{n})$，下邊引入一種篩法，可以將復雜度降為$O(nlogn)$.

篩法：
一個非素數(shù)，肯定可以被它的約數(shù)整數(shù)，那枚舉約數(shù)把約束的倍數(shù)標記，未被標記的數(shù)就是質數(shù)

代碼

void is_primes(int n) {for(int i=2;i<=n;i++){ for(int j=i;j<=n/i;j++){ v[i*j]=1;}}} //復雜度計算：n(1+1/2+1/3+……)調和級數(shù)

代碼優(yōu)化-埃氏篩

剛剛那個會有很多重復標記，比如24，在i=2（212）的時候標記一次，在i=4（46）的時候標記一次
這次優(yōu)化減少了部分重復計算
從質數(shù)的倍數(shù)都為合數(shù)的角度（剛剛是1-n所有數(shù)的倍數(shù)，由唯一分解定理可知，合數(shù)一定可以分解為素數(shù)的乘積），每次只標記素數(shù)的倍數(shù)，因為合數(shù)的話一定可以寫為素數(shù)相乘的形式，在素數(shù)時被標記過一次，如果合數(shù)再標記一次就會重復。

void is_primes(int n) {for(int i=2;i<=n;i++){ //是不是素數(shù)，初始化均為素數(shù)0if(v[i]) continue;//是素數(shù)的話就開始標記for(int j=i;j<=n/i;j++){ v[i*j]=1;}}} //復雜度：O（nloglogn）

歐拉篩（繼續(xù)優(yōu)化）

上邊的方法還是會有重復，比如12，在i=4（3）、6（2）的時候都會被標記一次，所以可以每次用一個數(shù)最小的質因子去篩掉合數(shù)（用素數(shù)去篩合數(shù)）且只用最小質因子去一次就行（比如12，只用素數(shù)2篩一次也就是只在62的時候再篩（更大的倍數(shù)i乘以更小的素數(shù)計算出12），所以要達到內層循環(huán)在乘完42就break的效果）

void is_primes(int n) {for(int i=2;i<=n;i++){ if(!v[i]) primes[++cnt]=i; //，初始化為0代表全是素數(shù)，i是素數(shù)for(int j=1;j<=cnt&&i*primes[j]<=n;j++){ v[i*primes[j]]=1; //所有質數(shù)的i倍，從最小倍開始，防止重復if(i%primes[j]==0)break;//如果i是prime的倍數(shù)的話//每個合數(shù)只被它的最小質因子篩一次//比如：12當i=12；prime=2（指的是prime是最小質因子而不是外層循環(huán)，外層循環(huán)代表的是倍數(shù)）的時候24才會被篩掉，所以i=8時對應prime=3會break掉（也就是i=8除以2為整數(shù)的時候）// 整體的來講，i是prime[j]的倍數(shù)時，i = kprime[j]，若不break繼續(xù)算 i乘以下一個，則i * prime[j+1] = prime[j] * k prime[j+1]，這里prime[j]是最小的質因子，也就是算了兩次，當i = k * prime[j+1]時會多重復了一次，所以才跳出循環(huán)。}}} //復雜度：O（n）

牛牛與LCM

（C++庫中自帶求最大公因子函數(shù)，可以直接拿來用）

#include<bits/stdc++.h> using namespace std; //若干個數(shù)，不是兩個數(shù) int lcm(int a,int b) {return a*b/__gcd(a,b); } int main() {int n;cin>>n;int *a=(int *)malloc(sizeof(int)*n);for(int i=0;i<n;i++){cin>>a[i];}int x;cin>>x; //這里要開long longlong long ans=1;for(int i=0;i<n;i++){//x是a[i]的倍數(shù)//不僅要是倍數(shù)還要是最小公倍數(shù)if(x%a[i]==0){ans=lcm(ans,a[i]);}}if(ans==x){cout<<"Possible";}elsecout<<"Impossible";return 0; }

Sum of Consecutive Prime Numbers

這個題涉及兩個知識點，求1~n的素數(shù)有哪些，上邊已經(jīng)講解過歐拉可以達到線性復雜度；另一個點就是在一串從小到大的數(shù)組中，找到和為x的一段，起初看到的時候，基于現(xiàn)有的知識，首先想到的是前綴和，也就是說：先求出前綴和序列，然后借助兩個指針表示所選取的序列，指針所指兩個前綴和序列對應數(shù)做減法得到指針之間這段序列的和，通過移動指針來得到最終結果（指針的初始位置均指向第一個數(shù)，若所指段和小于x，則右指針右移，若大于則左指針右移）。
但是看完題解，學到了基于滑動窗口的方法做這個題，整體思路一樣，借助兩個指針，通過移動來找到最終結果，初始sum值即為第一個數(shù)，當右指針右移時sum加當左指針右移時sum減，sum與x比較，同樣可以得到最終結果，并且省去了一個做前綴和的過程。

//題目給出了n的上限，且如果每次只按照當前n值找素數(shù)的話，會比較麻煩，所以直接一次性計算到上限 #include<bits/stdc++.h> using namespace std;int main() {//復習下，先不要看之前的筆記，需要維護一個素數(shù)數(shù)組和結果數(shù)組int prime[int(4e7)+1];bool is[int(4e7)+1];//開兩個int，空間會超，改成boolint cnt=0;memset(prime,0,sizeof(int)*(int(4e7)+1));memset(is,0,sizeof(bool)*(int(4e7)+1));for(int i=2;i<=int(4e7);i++){if(!is[i])prime[++cnt]=i;for(int j=1;j<=cnt&&i*prime[j]<=int(4e7);j++){is[i*prime[j]]=1;if(i%prime[j]==0)break;}}int T;cin>>T;int flag=1;while(flag<=T){flag++;int n;cin>>n;int l=1;int r=1;int ans=0;int sum=prime[1];for(;l>=1 && r<=cnt&&l<=r;){if(sum>=n){if(sum==n)ans++;sum-=prime[l];l++; }else if(sum<n){//這里順序不要反了啊r++;sum+=prime[r];}}cout<<ans<<endl; }return 0; }

Prime Distance（區(qū)間篩）

在素數(shù)判定中有提到，只用循環(huán)至$\sqrt{n}$，那么同理，一個數(shù)n的最小質因子一定小于等于$\sqrt{n}$（同樣反證法），也就是說，我們僅需要知道2~$\sqrt{n}$的素數(shù)，就可以篩選1~n

這個題一定要記得long long！！

//這個題目和上個題目不一樣之處在于，開不出來2的31次方的數(shù)組，并且篩到2的31次方的話即使是線性復雜度也會超時 //所以要做區(qū)間篩 #include <bits/stdc++.h> using namespace std; const int N=1e6+10; //只篩選出該范圍內的素數(shù)就行 const int range=46341+10; int prime[range]; bool is[range]; int p[N]; int max(long long a,long long b) {return a>b?a:b; } int main() {int cnt=0;memset(is,0,sizeof(int)*(range));for(int i=2;i<=range-10;i++){if(!is[i])prime[++cnt]=i;for(int j=1;j<=cnt&&i*prime[j]<=range-10;j++){is[i*prime[j]]=1;if(i%prime[j]==0)break;}}int T;cin>>T;long long r;long long l;while(T--){memset(p,0,sizeof(int)*(N));cin>>l>>r;//篩區(qū)間的時候用埃氏篩，歐拉篩會超時//因為直接按照倍數(shù)標記就行了，歐拉的話還要循環(huán)至質因數(shù)最小的那個倍數(shù)/*for(int i=max(2,l/prime[cnt]);i<=r/2+1;i++){for(int j=1;j<=cnt&&i*prime[j]>=l&&i*prime[j]<=r;j++){p[i*prime[j]-l]=1;if(i%prime[j]==0)break;}}*/for (long long i = 1; i <= cnt && prime[i] <= r; i++) {long long w = (l + prime[i] - 1) / prime[i];//第一個數(shù)是i的多少倍for (long long j = max(2, w); prime[i] * j <= r; j++)p[prime[i] * j - l] = 1;}vector<long long int > pri;for (long long i = max(2, l); i <= r; i++) { if (!p[i - l]) pri.push_back(i);p[i - l] = 0;}/*for(int i=0;i<N;i++){if(i+l>r)break;if(p[i]==0)pri.push_back(i);}*/if(pri.size()<=1){cout<<"There are no adjacent primes."<<endl;continue;}else{pair<long long,long long> min={0x3f3f3f3f3f,-1},max={-1,-1};for(long long i=0;i<pri.size()-1;i++){if(pri[i+1]-pri[i]>max.first){max.first=pri[i+1]-pri[i];max.second=i;}if(pri[i+1]-pri[i]<min.first){min.first=pri[i+1]-pri[i];min.second=i; }}cout<<pri[min.second]<<','<<pri[min.second+1]<<" are closest, "<<pri[max.second]<<','<<pri[max.second+1]<<" are most distant."<<endl;continue;}}return 0; }

實現(xiàn)唯一分解定理

就是從最小的素數(shù)開始一個一個除

for(int i=1;i<=cnt&&i<sqrt(n);i++) {while(n%prime[i]==0){a[c++]=prime[i];n=n%prime[i];} }

X-factor Chains

題中要求序列盡可能地長，也就是所有$a_{i+1}=t?a_i$中的t都要盡量的小，換個思路，質數(shù)是不能再分的，也就是說如果4*a可以寫作$2?2?a$從而達到t最小的效果，所以這道題就是實現(xiàn)唯一分解定理，然后對素數(shù)計算全排列

總結

以上是生活随笔為你收集整理的数论基础入门的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內容還不錯，歡迎將生活随笔推薦給好友。