文章目錄
- 前言
- 一、最大公約數(gcd)
- 二、最小公倍數（lcm）
- 三、多個數的最大公約數與最小公倍數
- 四、取模運算的一些性質
- 五、快速冪與二分法
前言
今天的主要內容是最大公約數與最小公倍數的求法以及相關事宜
一、最大公約數(gcd)
求最大公約數有三種辦法
1.暴力列舉法，代碼如下：
int a,b;int gcd=0;
cin>>a>>b;
for(int i=1;i<min(a,b);i++)
if(a%i==0&&b%i==0)
if(i>gcd)
gcd=i;
cout<<gcd<<endl;
優點：比較好想，直接粗暴
缺點：回圈次數較多，如果輸入資料范圍較大則容易超時
2.輾轉相除法
首先舉個例子吧，比如找 1112 和 695 的最大公約數，
首先，用較大的數字對較小的數字取余，也就是進行mod操作
1112 mod 695 = 417（然后用除數695和余數417進行mod操作）
695 mod 417 =278 （回圈往復，用除數除以余數）
417 mod 278 = 139 （繼續）
278 mod 139 = 0 （當取余結果為0時，停止該程序）
也就是說，278可以被139整除，
當余數為0時，最后一個除數139 就是1112和695的最大公約數，
代碼實作如下
int gcd(int a,int b){
if(a%b!=0)
return gcd(b,a%b);
else return b;
}
//此處省略main函式
int a,b,t;
cin>>a>>b;
if(a<b){
t=a;
a=b;
b=t;
}
int ans=gcd(a,b);
cout<<ans<<endl;
3.更相減損術
主要思想：
與輾轉相除法類似，用較大數減去較小數，若不為零，則用減數減去所得結果，如此回圈，
代碼如下：
int gcd (int a,int b){
if (a-b!=0)
return gcd(b,a-b);
else return b;
}
//此處省略main函式
int a,b,t;
cin>>a>>b;
if(a<b){
t=a;
a=b;
b=t;
}
int ans=gcd(a,b);
cout<<ans<<endl;
缺點：如果兩個數大小相差過大，可能導致需要回圈相減的次數增加，從而使得演算法復雜度退化為o（n）；相比之下，輾轉相除法的演算法復雜度更加穩定，始終為o（lg n）；
4.簡單粗暴直接法
其實，萬能的c++為我們配置了一個強大的函式，可以直接求出最大公約數，具體操作如下
cout<<__gcd(a,b)<<endl;
哈哈哈哈有沒有被驚到
頭檔案是
#include <algorithm>
當然你要非得偷懶用萬能頭
#include<bits/stdc++.h>
誰也攔不住你對吧，哈哈
二、最小公倍數（lcm）
求解最小公倍數的時候一般要先求出最大公約數
然后就可以套公式啦
lcm（a,b）=(a*b)/gcd(a,b)
也就是a,b的最小公倍數就是a和b的乘積除以a和b的最大公因數
代碼如下
這么簡單你讓我怎么給你寫代碼
好了，言歸正傳，有一件事情需要大家注意，就是計算的順序問題，如果直接a*b，在資料較大的時候容易溢位，導致錯誤的結果（WA），所以保險起見，我們一般都是先除再乘，
lcm(a,b)=a/gcd(a,b)*b
三、多個數的最大公約數與最小公倍數
其實也很簡單，具體思路就是，先求出前兩個數的最大公約數，再用這個數與下一個數進行求取最大公約數的操作，反復回圈，
代碼實作如下：
//假設有num個數
int x[num+10];
int gcd(int a,int b){
if(a%b!=0)
return gcd(b,a%b);
else return b;
}
//此處省略main函式
for(int i=0;i<num;i++)
cin>>x[i];
int k=x[0];
for(int i=1;i<num;i++)
k=gcd(k,x[i]);
cout<<k<<endl;
多個數的最小公倍數求法與此類似，也是先求出兩個數的最小公倍數，再用所求得的數與下一個數進行求取最小公倍數，如此回圈往復，
代碼如下：
//假設有num個數
int x[num+10];
int lcm(int a,int b){
int k=__gcd(a,b);
return a/k*b;
}
int lcm(int a,int b)
//此處省略main函式
for(int i=0;i<num;i++)
cin>>x[i];
int k=x[0];
for(int i=1;i<num;i++){
k=lcm(k,x[i]);
}
cout<<k<<endl;
四、取模運算的一些性質
為了防止資料溢位，我們通常會根據取模運算的一些性質來對式子進行一些優化，比如：
(a + b) % p = (a % p + b % p) % p
(a * b) % p = (a % p * b % p) % p
a ^ b % p = ((a % p)^b) % p（或者用下面的快速冪）
五、快速冪與二分法
舉個例子：求a求 a^b % m的值
這個用普通演算法我就不說了，時間復雜度O（b），也就是上面的a ^ b % p = ((a % p)^b) % p一直回圈，
而快速冪的核心就是怎么迅速的將a的b次冪求出來，
即
1）當b是奇數時，那么有 a^b = a * a^*(b-1)
2）當b是偶數時，那么有 a^b = a^(b/2) * a^(b/2)
代碼如下：
typedef long long ll;
ll Fastpow(ll a, ll b, ll m){
if(b == 0)
return 1;
else if(b & 1)//b & 1等價于 b % 2==1
return a * Fastpow(a, b - 1, m) % m;
else{
ll num = Fastpow(a, b/2, m) % m;
return num * num % m;
}
注：
1.未考慮b<0的情況，如體中需要，自行加入即可，
2.作者水平有限，不足之處敬請指出，
3.聽說給我點贊收藏的高數都打90多？？
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/240852.html
標籤：其他