🔔由理論推導到代碼實踐逐步精準掌握數論 （一）
- 💓質數
- 🌟基本概念
- 🌟質數的判定——試除法
- 🌻例題描述
- 🌻參考代碼(C++版本)
- 🌻演算法模板
- 🌻疑難點剖析
- 🌟分解質因數
- 🌻例題描述
- 🌻參考代碼(C++版本)
- 🌻演算法模板
- 🌻疑難點剖析
- 🌟質數篩選
- 🌻例題描述
- 參考代碼(C++版本)
- 🌻演算法模板
- 🌻疑難點剖析
- 💓約數
- 🌟基本概念
- 🌟約數的判定——試除法
- 🌻例題描述
- 🌻參考代碼(C++版本)
- 🌻演算法模板
- 🌻疑難點剖析
- 🌟統計約數的個數
- 🌻例題描述
- 🌻參考代碼(C++版本)
- 🌻演算法模板
- 🌟統計約數的和
- 🌻例題描述
- 🌻參考代碼(C++版本)
- 🌻演算法模板
- 🌻公式推導
- 🌟歐幾里得演算法
- 🌻基本概念
- 🌻例題描述
- 🌻參考代碼(C++版本)
- 🌻演算法模板
- 💓總結
- 謝謝友友們耐心觀看啦~，若有偏頗，歡迎及時私信指出喔💖💖💖
- 基礎演算法持續更新中ing~
💓質數
🌟基本概念
| 如果一個正整數只能被1和自身整除，那么這個正整數就是質數(也稱素數),否則稱該正整數為合數 |
🌟質數的判定——試除法
🌻例題描述
🎇🎇🎇原題傳送門🎇🎇🎇
🌻參考代碼(C++版本)
#include <iostream>
#include <algorithm>
using namespace std;
int n;
bool is_prime(int n)
{
//0 和 1既不是質數，也不是合數
if(n < 2) return false;
for(int i = 2;i <= n / i ;i++)
if(n % i == 0) return false;
return true;
}
int main()
{
//輸入
scanf("%d",&n);
while(n--)
{
//呼叫函式 + 輸出
int t;
scanf("%d",&t);
if(is_prime(t)) puts("Yes");
else puts("No");
}
}
🌻演算法模板
試除法判定質數
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;
}
🌻疑難點剖析
一、演算法實作思路
掃描2~
N
\sqrt{N}
N
?之間的所有整數，依次檢查它們能否整除N，若都不能整除，那么N是質數，否則N是合數，所以時間復雜度是O(
N
\sqrt{N}
N
?)
二、演算法實作的優化
| 這個演算法從暴力的角度走，是可以直接從2列舉到N-1的，只要這里面都沒有能夠整除N的，那么就可以確定這個N是質數，但是這種做效率挺慢的，時間復雜度是O(N) |
| 比如現在N是17，先去整除4進行嘗試，假如再嘗試8, 12，16其實都沒有意義了，因此就根據性質進行優化， |
| 乘法運算中，乘數 x 另一個乘數 = 積， 當 n 能夠整除 d 的時候，結果是 n/d,同時，它也就是另一個乘數，那么n也肯定是能夠整除n/d的， 因為我們是從2開始列舉，d依次被賦值為2,3，，，所以d < = n/d，依據這個實作對列舉區間的縮小 |
🌟分解質因數
| 算識訓本定理： 對于任何一個大于1的正整數都能唯一分解為有限個質數的乘積，可寫作： |
N = P1c1 P2c2 …Pmcm
其中ci都是正整數，Pi都是質數，且滿足P1 < P2 < … < Pm
🌻例題描述
🎇🎇🎇原題傳送門🎇🎇🎇
🌻參考代碼(C++版本)
#include <iostream>
#include <algorithm>
using namespace std;
void divide(int n)
{
//試除法列舉所有的數
for(int i = 2;i <= n / i;i++)
if(n % i == 0)
{
int s = 0;
while(n % i == 0)
{
n /= i;
s++;
}
printf("%d %d\n",i,s); //要清楚i才是底數
}
if(n > 1) printf("%d %d\n",n,1);
puts("");
}
int main()
{
//輸入
int n;
scanf("%d",&n);
while(n--)
{
//調函式
int x;
scanf("%d",&x);
divide(x);
}
return 0;
}
🌻演算法模板
一、演算法實作流程圖：
二、演算法的代碼實作：
試除法分解質因數
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;
}
🌻疑難點剖析
一、明白題目需求
| 題目要的是將傳入的資料分解為底數是/質數，指數是整數，分解結果的乘積等于原資料，輸出的時候，要從小到大排列， |
例如：
6就是21 x 31，因此就輸出 2 1和3 1
48就是24 x 31，因此就輸出2 4 和 3 1
二、指數的獲取
8 = 23 = 2 x 2 x 2;
| 那么在代碼層面，我們可以采用逆向思維，倒著對8進行運算，統計它進行的除法次數，也就是相乘的次數了，同時，也就是指數了， |
🌟質數篩選
🌻例題描述
🎇🎇🎇原題傳送門🎇🎇🎇
參考代碼(C++版本)
// 埃氏篩選法
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e6 + 10;
int primes[N],cnt;
bool st[N];
void get_primes(int n)
{
for(int i = 2;i <= n;i++)
{
if(!st[i])
{
primes[cnt++] = n;
//利用現有的質數，將質數的倍數去掉
for(int j = i+i; j <= n;j += i) st[j] = true;
}
}
}
int main()
{
//輸入
int n;
cin >>n;
//呼叫函式
get_primes(n);
//輸出
cout << cnt <<endl;
return 0;
}
//線性篩選法 演算法原理：n只會被最小質因子篩掉
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e6 + 10;
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++)
{
//把prims[j] * i篩掉
st[primes[j] * i] = true;
if(i % primes[j] == 0) break; //primes[j]一定是i的最小質因子
}
/*
1、i % pj == 0
pj一定是i的最小質因子，pj一定是pj*i的最小質因子
2、i % pj != 0
pj一定小于i的所有質因子，pj也一定是pj * i的最小質因子
*/
}
}
int main()
{
//輸入
int n;
cin >>n;
//呼叫函式
get_primes(n);
//輸出
cout << cnt <<endl;
return 0;
}
🌻演算法模板
一、埃氏篩法——用當前已有的質數去消去它們的倍數
| 首先，將2到n范圍的所有整數獲取到，其中，最小的數字2是質數，將2的所有倍數劃去，表中剩余的數字中，最小的是3，它不能被更小的整除，所有它是質數，再將所有3的倍數劃去，以此類推如果表中剩余的最小數字是m時，m就是質數，然后將表中所有m的倍數都劃去，像這種反復操作，就能夠依次列舉n以內的質數， |
舉個栗子：
1.1、 演算法實作流程如下：
1.2、演算法代碼實作：
埃氏篩法求素數
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; j <= n; j += i)
st[j] = true;
}
}
1.3、演算法的時間復雜度 = O(NloglogN)
二、線性篩法
| 線性篩選的核心是—— 傳入的整數n只會被最小質因子篩掉 |
2.1、演算法實作流程：
2.2、演算法代碼實作：
線性篩法求素數
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;
}
}
}
2.3、演算法時間復雜度 = O(N)
🌻疑難點剖析
| 清楚primes陣列和st陣列是分別用來維護素數集合和被篩除資料的集合 |
💓約數
🌟基本概念
| 若整數 n 除以整數 d 的余數為零，即 d 能夠整除 n,則稱 d 是 n 的約數，n 是 d 的倍數，記作：d|n |
🌟約數的判定——試除法
🌻例題描述
🎇🎇🎇原題傳送門🎇🎇🎇
🌻參考代碼(C++版本)
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
vector<int> get_divisors(int n)
{
vector<int> res;
for(int i = 1; i <= n / i;i++)
if(n % i == 0)
{
res.push_back(i);
if(i != n / i) res.push_back(n / i);
}
//按照從小到大的順序輸出它的所有約數，
sort(res.begin(),res.end());
return res;
}
int main()
{
int n;
cin >> n;
while(n--)
{
int x;
cin >> x;
auto res = get_divisors(x);
for(auto t: res) cout << t << ' ';
cout << endl;
}
return 0;
}
🌻演算法模板
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;
}
🌻疑難點剖析
一、優化
| 最暴力的做法依舊是可愛的列舉，從1列舉到x，但是和求質數演算法一樣，當3是約數的時候，就不必去列舉12,15等等 |
二、結果統計
if (x % i == 0)
{
res.push_back(i);
if (i != x / i) res.push_back(x / i);
}
| 利用的性質是：兩數相乘，積 = 乘數 x 另一個乘數， x % i == 0說明 i 是 x 的一個乘數，則另一乘數就是 x/i，將其加入集合 |
🌟統計約數的個數
🌻例題描述
🎇🎇🎇原題傳送門🎇🎇🎇
🌻參考代碼(C++版本)
#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;
typedef long long LL;
const int mod = 1e9 + 7;
int main()
{
//輸入
int n;
cin >> n;
//用STL容器開一個哈希表存分解出來的數的底數和指數
unordered_map<int,int> primes;
while(n--)
{
int x;
cin >> x;
//分解質因數的演算法模板來分解這個輸入的x
for(int i = 2; i <= x / i;i++)
while(x % i == 0)
{
x /= i;
primes[i] ++;//使i這個質因數的指數加1
}
if(x > 1) primes[x] ++; //對傳入的x直接就是質因子的情況進行處理
}
//輸出
LL res = 1;
for(auto prime : primes) res = res * (prime.second + 1) % mod;
cout << res << endl;
return 0;
}
🌻演算法模板
求約數個數演算法實作流程：
🌟統計約數的和
🌻例題描述
原題傳送門
🌻參考代碼(C++版本)
#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;
typedef long long LL;
const int mod = 1e9 + 7;
int main()
{
//輸入
int n;
cin >> n;
//開一個哈希表存分解出來的數的底數和指數
unordered_map<int,int> primes;
while(n--)
{
int x;
cin >> x;
//分解這個輸入的x
for(int i = 2; i <= x / i;i++)
while(x % i == 0)
{
x /= i;
primes[i] ++;//i這個質因數的指數加1
}
if(x > 1) primes[x] ++;
}
//結合公式輸出
LL res = 1;
for(auto prime : primes)
{
//p是質數，也就是公式中的底數，a是質數出現的個數，也就是公式中的指數
int p = prime.first , a = prime.second;
LL t = 1;
while(a--) t = (t * p + 1) % mod;
res = res * t % mod;
}
cout << res << endl;
return 0;
}
🌻演算法模板
求約數和演算法實作流程：
🌻公式推導
看完求約數個數的演算法實作流程和求約數和的演算法實作流程小伙伴們心中應該能很清晰的感受到，大致是相似的，只是最后輸出時運用的公式不一樣，
數論這章了，很像高中的數學題了，知道那個性質，明白那個公式，大抵就能夠做出來的
在查閱資料之后，發現李煜東老師的《演算法競賽——進階指南》中的對兩個公式的推導十分清晰，故筆者就不畫蛇添足、班門弄斧了
筆者就結合例題來具體演示喔
求約數個數的公式的意思，就是將得到的質因數再分解，例如25中，20是約數，21是約數，22是約數，23是約數，24是約數，25是約數，所以就有5+1個約數，即公式中的c1+1，對于其他分解出來的質因數也是同理分解，
求約數和的公式意思，將分解出來的質因數，同時也是這個正整數乘積96的約數，它們之間的和是多少，
25 和 31 組成的約數應該有：20、 21 、 22、23 、 24 、25 、 30 、 31，
那么這些它們組成的約數和應試是
20 x （ 30 + 31 ） + 21 x （ 30 + 31）+…+ 2^5 x ( 30 + 31 ）
經過整理，就可以得到形容李老師書中的公式：
( 20+ 21 + 22+ 23 + 24 +25 ) x( 30 + 31)
即:（1+ 21 + 22+ 23 + 24 +25 ）x (1 + 31)
演示完畢啦
🌟歐幾里得演算法
🌻基本概念
公約數：
| 若自然數 d 同時是自然數 a 和 b的公約數，則稱 d 是 a 和 b 的公約數，在所有 a 和 b 的公約數中最大的一個，稱為 a 和 b 的最大公約數，記作 gcd(a,b) |
公倍數：
| 若自然數 m 同時是自然數 a 和 b的公約數，則稱 m 是 a 和 b 的公倍數，在所有 a 和 b 的公約數中最小的一個，稱為 a 和 b的最小公倍數，記作 lcm(a,b) |
🌻例題描述
🎇🎇🎇原題傳送門🎇🎇🎇
🌻參考代碼(C++版本)
#include <iostream>
using namespace std;
//歐幾里得演算法，亦稱為輾轉相除法
int gcd(int a,int b)
{
return b ? gcd(b, a%b):a;
}
int main()
{
int n;
scanf("%d",&n);
while(n--)
{
int a, b;
scanf("%d%d",&a,&b);
printf("%d\n",gcd(a,b));
}
return 0;
}
🌻演算法模板
| 通俗來說，就把b定為除數，只要它還能夠進行除法運算，就把它拋到函式中，與a進行除法運算，所有歐幾里得演算法也叫輾轉相除法， |
💓總結
| 一、質數、約數、公約數、公倍數這些我們曾經學過的數學知識要清楚喔，后續質數的篩選、分解，約數的統計都是在這些基礎知識上開展的， |
| 二、對于數論的題，小伙伴假如把我之前寫的圖論的文章和這篇對比，應該可以很清楚的感受到，演算法模板這塊的內容不再是清爽的演算法的執行流程了，取而代之的是一兩行公式的代碼或者公式的推導理解，因為數論的題就和數學十分貼貼了，對公式的理解和運用就轉變為了核心，所以需要自己下來落實對公式的推導，加深理解，才更好記憶住，最后在賽場上，大殺四方 |
謝謝友友們耐心觀看啦~，若有偏頗，歡迎及時私信指出喔💖💖💖
基礎演算法持續更新中ing~
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/413958.html
標籤：其他