2024第十五屆藍橋杯大賽軟件賽省賽C/C++ 大學 B 組

記錄刷題的過程、感悟、題解。
希望能幫到，那些與我一同前行的，來自遠方的朋友😉

大綱：

?1、握手問題-（解析）-簡單組合問題（別人叫她鴿巢定理）😇，感覺叫高級了

?2、小球反彈-（解析）-簡單物理問題，不太容易想

?3、好數-（解析）-簡單運用分支計算

?4、R 格式-（解析）-高精度，不是快速冪😉

?5、寶石組合-（解析）-lcm推論（gcd、lcm結合）

?6、數字接龍-（解析）-DFS（藍橋專屬、每年必有一道）

?7、拔河-（解析）-定一端，動一端😎

題目：

1、握手問題

問題描述

小藍組織了一場算法交流會議，總共有?50?人參加了本次會議。在會議上，大家進行了握手交流。按照慣例他們每個人都要與除自己以外的其他所有人進行一次握手 (且僅有一次)。但有?7?個人，這?7?人彼此之間沒有進行握手 (但這?7?人與除這?7?人以外的所有人進行了握手)。請問這些人之間一共進行了多少次握手?

注意?A?和?B?握手的同時也意味著?B?和?A?握手了，所以算作是一次握手。

答案提交

這是一道結果填空的題，你只需要算出結果后提交即可。本題的結果為一個整數，在提交答案時只填寫這個整數，填寫多余的內容將無法得分。

// 我看大家都叫他鴿巢定理（就是簡單的組合問題）
// 其實只需要枚舉一下就行了
// 只需要枚舉一下就行了
// 舉個例子：
// 給所有1~50個人，排一個編號。
// 第50個人，與其他49個人握手，
// 第49個人，與其他48個人握手。（因為第50個人，已經跟他握過了）
// ...
// 第8個人，給其他7個人握手
// 第7個人，就不能跟剩下的6個人握手了（題目：這?7?人彼此之間沒有進行握手）
// 同理，第6個、第5個...
// 因為這個7個人之間，不能相互握手。

#include <iostream>
using namespace std;int main()
{int sum=0;for(int i=7; i<=49; ++i) sum+=i;cout<<sum<<endl;return 0;
}

2、小球反彈

問題描述

有一長方形，長為?343720 單位長度，寬為?2333332 單位長度。在其內部左上角頂點有一小球 (無視其體積)，其初速度如圖所示且保持運動速率不變，分解到長寬兩個方向上的速率之比為?dx:dy=15:17。小球碰到長方形的邊框時會發生反彈，每次反彈的入射角與反射角相等，因此小球會改變方向且保持速率不變（如果小球剛好射向角落，則按入射方向原路返回）。從小球出發到其第一次回到左上角頂點這段時間里，小球運動的路程為多少單位長度？答案四舍五入保留兩位小數。

答案提交

這是一道結果填空的題，你只需要算出結果后提交即可。本題的結果為一個小數，在提交答案時只填寫這個小數，填寫多余的內容將無法得分。

其實這道題非常簡單的啦，畫個圖，就能解決了。

只要畫個圖、然后去找他的鏡像對稱就行。（不斷的補充方格就OK嘍）

咱們暫定，咱們的速度是1，于是沒t秒，運行t個單位。
最后的結果需要乘以2，比較要原路返回🔙。

#include <bits/stdc++.h>
#define ll long longusing namespace std;
int main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); ll t = 1;ll x=0,y=0; while(1){x=17*t;y=15*t;if(x%233333==0&&y%343720==0) break;else t++;}double len = 2*sqrt((x*x)+(y*y));printf("%.2lf",len);return 0; 
}

3、好數

問題描述

一個整數如果按從低位到高位的順序，奇數位 (個位、百位、萬位????) 上的數字是奇數，偶數位 (十位、千位、十萬位????) 上的數字是偶數，我們就稱之為 “好數”。

給定一個正整數?N，請計算從 1 到?N?一共有多少個好數。

輸入格式

一個整數?N。

輸出格式

一個整數代表答案。

樣例輸入 1
24
樣例輸出 1
7
樣例輸入 2
2024
樣例輸出 2
150
樣例說明

對于第一個樣例，24?以內的好數有?1、3、5、7、9、21、23，一共?7?個。

評測用例規模與約定

對于?10%?的評測用例，1≤N≤100?。

對于?100%的評測用例，1≤N≤10^7 。

其實.....這道題，真的很簡單，如果做不出來，只能說，練的少。

其實就是簡單的模擬。

當然如果期間你用reverse反轉的話，一定會超時。（先把數字轉化為字符串，然后將字符串反轉一下，奇數位，必須是偶數；偶數位，必須是奇數。）

這是我在網上看的一哥們寫的，只能說分支被他玩明白了😇

#include <stdio.h>
int main()
{int n,i;scanf("%d",&n);for(;n>0;n--){for(int m=n;m>0;){if(m%2!=0)m/=10;else break;if(m%2==0)m/=10;else break;if(m==0)i++;}}printf("%d",i);return 0;
}

4、R 格式

問題描述

小藍最近在研究一種浮點數的表示方法：R?格式。對于一個大于 0 的浮點數?d，可以用?R?格式的整數來表示。給定一個轉換參數?n，將浮點數轉換為?R?格式整數的做法是:

將浮點數乘以?2^n；

四舍五入到最接近的整數。

輸入格式

一行輸入一個整數?n?和一個浮點數?d，分別表示轉換參數，和待轉換的浮點數。

輸出格式

輸出一行表示答案：d?用?R?格式表示出來的值。

樣例輸入
2 3.14
樣例輸出
13
樣例說明

3.14×22=12.56，四舍五入后為?13。

評測用例規模與約定

對于?50% 的評測用例：1≤n≤10,1≤ 將?d?視為字符串時的長度 ≤15。

對于?100% 的評測用例：1≤n≤1000,1≤ 將?d?視為字符串時的長度?≤1024；保證?d?是小數，即包含小數點。

哎，被這道題目給騙了😇，第一眼看上去，我還以為是快速冪呢。

其實本題本質上，就是一道高精度題目。

在藍橋杯中，高精度是一個高頻考點，我在最下部，高精度各種計算的模板。?::傳送門::

本題，實際上就是，不斷乘以2，當然啦，要用高精度的乘法模版乘。循環n次

當然，要先記錄一下數點的位置，然后減去。

#include <bits/stdc++.h>
using namespace std;// 定義兩個向量 A 和 B 用于存儲高精度數字
vector<int> A, B;// 函數 get 用于實現高精度乘法，將 A 和 B 相乘的結果存回 A
void get() {// 結果向量 C 的大小是 A 和 B 大小之和vector<int> C(A.size() + B.size()); // 逐位相乘并累加到 C 中for(int i = 0; i < A.size(); ++i)for(int j = 0; j < B.size(); ++j)C[i + j] += A[i] * B[j];    // 處理進位int carry = 0;for(int i = 0; i < C.size(); ++i) {carry += C[i];C[i] = carry % 10;carry /= 10;    }// 去除前導 0，保留有效數字while(C.size() > 1 && C.back() == 0) C.pop_back(); A = C;
}// 主函數
int main() {int n;string str;// 輸入轉換參數 n 和待轉換的浮點數（以字符串形式輸入）cin >> n >> str;// 將字符串反轉，方便處理小數部分reverse(str.begin(), str.end()); int pla = 0;// 找到小數點的位置for(int i = 0; i < str.size(); ++i) if(str[i] == '.') {pla = i; break;}// 其實這里能改進的，好在該數只有一個'.'，因為 erase 函數的參數如果是字符，它會刪除字符串中所有等于該字符的字符。// 而我們只需要刪除一個小數點，也可使用 erase 函數的另一個重載版本，傳入位置參數// 例如：str.erase(pla, 1);// 將字符串中的數字字符轉換為整數存入向量 A，跳過小數點for(int i = 0; i < str.size(); ++i) if(str[i] != '.') A.emplace_back(str[i] - '0'); // 向量 B 初始化為 [2]，用于后續的乘法操作B.emplace_back(2);// 執行 n 次乘法操作，即乘以 2 的 n 次方while(n--) get();// 進行四舍五入操作，如果小數點后一位大于等于 5，則進位if(A[pla - 1] >= 5) {int carry = 1;for(int i = pla; i < A.size(); ++i) {carry += A[i];A[i] = carry % 10;carry /= 10;if(carry == 0) break;}if(carry != 0) A.emplace_back(carry);}// 將結果向量 A 反轉回正常順序reverse(A.begin(), A.end());// 去除小數部分，因為題目要求輸出整數while(pla--) A.pop_back();// 輸出最終結果for(int i : A) cout << i;return 0;
}

5、寶石組合

輸入格式

第一行包含一個整數?N?表示寶石個數。

第二行包含?N?個整數表示?N?個寶石的 “閃亮度”。

輸出格式

輸出一行包含三個整數表示滿足條件的三枚寶石的 “閃亮度”。

樣例輸入
5
1 2 3 4 9
樣例輸出
1 2 3
評測用例規模與約定

對于?30% 的評測用例：3≤N≤100,1≤Hi≤1000。

對于?60% 的評測用例：3≤N≤2000。

對于?100%的評測用例：3≤N≤10^5,1≤Hi≤10^5 。

像這種題目，要學會做減法，（見好就收）

前提是，你要知道gcd與lcm都是怎么求的，否則一切都是白談。點擊了解?:: 傳送門?::?

直接暴力，先拿個30%的分數，“字典序列最小”，也只是聽著唬人罷了。😉

首先，我先給出30%的分數，然后在給出100%的解法。

30%


#include <bits/stdc++.h>
using namespace std;
#define int long long
int gcd(int a, int b)
{if (b == 0)return a;return gcd(b, a % b);
}
int lcm(int a, int b)
{return a * b / gcd(a, b);
}
int gcd3(int a, int b, int c)
{return gcd(gcd(a, b), c);
}
int lcm3(int a, int b, int c)
{return lcm(lcm(a, b), c);
}
signed main()
{int n;cin >> n;vector<int> a(n), b(3);for (int i = 0; i < n; i++)cin >> a[i];sort(a.begin(), a.end());int ans = 0;for (int i = 0; i < n; i++){for (int j = i + 1; j < n; j++){for (int k = j + 1; k < n; k++){int s = a[i] * a[j] * a[k] * lcm3(a[i], a[j], a[k]) / (lcm(a[i], a[j]) * lcm(a[i], a[k]) * lcm(a[j], a[k]));if (s > ans){ans = s;b[0] = a[i];b[1] = a[j];b[2] = a[k];}}}}cout << b[0] << " " << b[1] << " " << b[2];return 0;
}

100%

其實本題最難的，就是把公式給推導出來

就是把推導成gcd(a,b,c)

:: 具體的推導方法?::

當你把公式推導出來之后，gcd。

首先在輸入的時候，推導出gcd最大為多少（根據gcd的性質）

然后不斷減減。

假設sum=gcd(a,b,c)，說明，a、b、c都是sum的倍數，然后題目就是根據這個推導出來的。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5+5;
signed main(){// 既然公式已經推導出來了，那就直接來個大的吧// gcd(a,b,c) 最大數，就是輸入的數字int n;cin>>n;vector<int> arr(N,0);int maxN = -1;for(int i=0; i<n; ++i) {int cnt;cin>>cnt; // 輸入數據 arr[cnt]++;maxN=max(maxN,cnt);}for(int i=maxN; i>=1; --i){int num=0,cnt[3],flag=0; // flag:有幾個數字for(int sum=i; sum<N; sum+=i){if(arr[sum]!=0){for(int k=0; k<arr[sum]&&flag<3; ++k){cnt[flag++]=sum; }}if(flag==3){cout<<cnt[0]<<" "<<cnt[1]<<" "<<cnt[2];return 0;}} }return 0;
}

6、數字接龍

問題描述

小藍最近迷上了一款名為《數字接龍》的迷宮游戲，游戲在一個大小為?N×N 的格子棋盤上展開，其中每一個格子處都有著一個?0…K?1 之間的整數。游戲規則如下：

從左上角?(0,0)?處出發，目標是到達右下角?(N?1,N?1) 處的格子，每一步可以選擇沿著水平/垂直/對角線方向移動到下一個格子。

對于路徑經過的棋盤格子，按照經過的格子順序，上面的數字組成的序列要滿足：0,1,2,…,K?1,0,1,2,…,K?1,0,1,2…。

途中需要對棋盤上的每個格子恰好都經過一次（僅一次）。

路徑中不可以出現交叉的線路。例如之前有從?(0,0) 移動到?(1,1) ，那么再從?(1,0) 移動到?(0,1) 線路就會交叉。

為了方便表示，我們對可以行進的所有八個方向進行了數字編號，如下圖 2 所示；因此行進路徑可以用一個包含?0…7 之間的數字字符串表示，如下圖 1 是一個迷宮示例，它所對應的答案就是：41255214。

現在請你幫小藍規劃出一條行進路徑并將其輸出。如果有多條路徑，輸出字典序最小的那一個；如果不存在任何一條路徑，則輸出??1。

輸入格式

第一行包含兩個整數?N,K 。

接下來輸入?N?行，每行?N?個整數表示棋盤格子上的數字。

輸出格式

輸出一行表示答案。如果存在答案輸出路徑，否則輸出??1。

樣例輸入
3 3
0 2 0
1 1 1
2 0 2
樣例輸出
41255214
樣例說明

行進路徑如圖?1?所示。

評測用例規模與約定

對于?80%?的評測用例：1≤N≤5 。

對于?100%?的評測用例：1≤N≤10,1≤K≤10 。

DFS千篇一律，😇😉，好像都是這個模版耶，稍稍總結一下！嘿嘿(～￣▽￣)～?

#include <bits/stdc++.h>
using namespace std;// 定義棋盤的最大尺寸，這里設置為 15，可根據實際需求調整
const int N = 1e1+5; // 棋盤的邊長 n 和數字循環的周期 k
int n, k; // 存儲棋盤上每個格子的數字
int arr[N][N]; // 表示八個方向在 x 軸上的偏移量
int fa1[] = {-1, -1, 0, 1, 1, 1, 0, -1}; 
// 表示八個方向在 y 軸上的偏移量
int fa2[] = {0, 1, 1, 1, 0, -1, -1, -1}; // 用于標記棋盤上的格子是否已經被訪問過
bool used[N][N]; // 用于標記兩個格子之間的連線是否已經存在，防止路徑交叉
bool edge[N][N][N][N]; // 存儲當前正在探索的路徑
vector<int> res; 
// 存儲找到的字典序最小的路徑
vector<int> t; // 深度優先搜索函數
// cur_x, cur_y 表示當前所在格子的坐標
// cnt 表示當前已經走過的步數（從 1 開始計數）
void dfs(int cur_x, int cur_y, int cnt) {// 如果已經走過了 n * n - 1 步（因為起點已經算走過了）并且到達了右下角if (res.size() == n * n - 1 && cur_x == n - 1 && cur_y == n - 1) {// 如果 t 為空或者當前路徑 res 的字典序小于 tif (t.empty() || res < t) {// 更新 t 為當前路徑 rest = res;}return;}// 遍歷八個方向for (int i = 0; i < 8; ++i) {// 計算下一個格子的坐標int x = cur_x + fa1[i], y = cur_y + fa2[i];// 如果下一個格子超出了棋盤范圍，跳過if (x < 0 || x >= n || y < 0 || y >= n) continue; // 如果下一個格子已經被訪問過，跳過if (used[x][y]) continue;// 如果是斜向移動（i % 2 == 1）并且當前路徑會與已有的路徑交叉，跳過if (i % 2 == 1 && (edge[cur_x][y][x][cur_y] || edge[x][cur_y][cur_x][y])) continue; // 如果下一個格子的數字符合當前步數的要求（按照 0 到 k - 1 的循環）if (cnt % k == arr[x][y]) { // 將當前方向加入路徑res.push_back(i);// 標記下一個格子為已訪問used[x][y] = true;// 標記當前格子和下一個格子之間的連線已存在edge[cur_x][cur_y][x][y] = true;// 遞歸地繼續搜索下一個格子dfs(x, y, cnt + 1);// 回溯，撤銷對下一個格子的訪問標記used[x][y] = false;// 回溯，撤銷當前格子和下一個格子之間的連線標記edge[cur_x][cur_y][x][y] = false;// 回溯，從路徑中移除當前方向res.pop_back();} } 
}int main() {// 輸入棋盤的邊長 n 和數字循環的周期 kcin >> n >> k;// 輸入棋盤上每個格子的數字for (int i = 0; i < n; ++i)for (int j = 0; j < n; ++j) cin >> arr[i][j];// 標記起點為已訪問used[0][0] = true;// 從起點 (0, 0) 開始進行深度優先搜索，步數為 1dfs(0, 0, 1);// 如果沒有找到符合要求的路徑if (t.size() == 0) cout << -1 << endl;else {// 輸出字典序最小的路徑for (int i : t) cout << i;}return 0;
}

7、拔河

問題描述

小明是學校里的一名老師，他帶的班級共有?nn?名同學，第?ii?名同學力量值為?aiai?。在閑暇之余，小明決定在班級里組織一場拔河比賽。

為了保證比賽的雙方實力盡可能相近，需要在這?nn?名同學中挑選出兩個隊伍，隊伍內的同學編號連續：{al1,al1+1,…,ar1?1,ar1} 和?{al2,al2+1,…,ar2?1,ar2}，其中?l1≤r1<l2≤r2。

兩個隊伍的人數不必相同，但是需要讓隊伍內的同學們的力量值之和盡可能相近。請計算出力量值之和差距最小的挑選隊伍的方式。

輸入格式

輸入共兩行。

第一行為一個正整數?n。

第二行為?n?個正整數?ai?。

輸出格式

輸出共一行，一個非負整數，表示兩個隊伍力量值之和的最小差距。

樣例輸入
5
10 9 8 12 14
樣例輸出
1
樣例說明

其中一種最優選擇方式：

隊伍 1：?{a1,a2,a3}，隊伍 2：{a4,a5}，力量值和分別為?10+9+8=27 ,?12+14=26，差距為?∣27?26∣=1 。

評測用例規模與約定

對于?20%?的評測用例，保證?n≤50。

對于?100% 的評測用例，保證?n≤10^3,ai≤10^9 。

大腦模擬一下，就是兩個不能重疊的區間，在相互亂動

而，現在，我們要做的，就是定一個區間，動一個區間。

當然，我不知道，會不會有人擔心，這樣做，會不會漏掉某些區間。

舉個例子。

假設共長10。

（以下，看不懂沒關系，直接跳過，把代碼復制下來問AI😄）

[0,1]區間，此時紅線在2這個節點。如下代碼遍歷時，只能定以2為左端點。

以下代碼是不是無法判斷[7、8]這個區間？后來是不是會被遺忘點。

完全沒必要擔心，因為[0,1]會被記錄到set中，后續等以7為左邊端點時，還能對比。

// 雙動態，定一，動一。
#include <bits/stdc++.h> 
#define ll long long
using namespace std;
const ll N = 1e3+5,Num=0x3f3f3f3f3f3f3f3f;
ll n;
vector<ll> arr(N,0);
vector<ll> sum(N,0);
ll minNum=0x3f3f3f3f3f3f3f3f; // 天哦，原來如此。 int main(){ // 如果定義成這個了，全局該如何避免。 ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); cin>>n;for(int i=1; i<=n; ++i) {cin>>arr[i];sum[i]=sum[i-1]+arr[i];		} set<ll> s;s.insert(Num); // 模擬插入最大值s.insert(-Num); // 模擬插入最小值 for(int i=2; i<=n; ++i){ // 中間線段 // 存入前綴和for(int j=1; j<=i-1; ++j) s.insert(sum[i-1]-sum[j-1]); // 左邊所有區間 // 匹配前綴和 for(int k=i; k<=n; ++k){ll k_sum = sum[k]-sum[i-1];auto it = s.lower_bound(k_sum); // 第一個大于or等于的數字// 目的是找到最相近的數minNum = min(minNum,abs(*it-k_sum));minNum = min(minNum,abs(*(--it)-k_sum)); }} cout<<minNum;return 0;
}

知識點：

1、鴿巢定理（抽屜原理）

基本原理：

常被用于證明存在性證明，和求最壞情況下的解。

存在性證明：連最壞情況都不存在解，所以情況也就肯定不存在解。

舉例：

其可以解釋許多有趣的現象（下文會解釋）：

世界上肯定有兩個人頭發數量一樣多
1500人中，至少有5個人的生日相同
n個人之間握手，一定有兩個人握手的次數相同。
任意6個人，其中至少有3個人互相不認識，或者互相認識

舉例子n個人握手問題，每個人必定會握手0~(n-1)次。所以必定有重復

具體6人問題：把這 6 個人看作 6 個頂點，每兩個頂點之間連一條邊。
如果兩個人互相認識，就把這條邊染成紅色；如果兩個人互相不認識，就把這條邊染成藍色。
那么問題就轉化為：在這個由 6 個頂點和它們之間的邊構成的圖中，一定存在一個同色的三角形（三條邊顏色相同的三角形），也就是要么有一個紅色三角形（代表三個人互相認識），要么有一個藍色三角形（代表三個人互相不認識）。

例題：

例題1：hdu1205 吃糖果
（隔板法）

假設N糖果數最多的一種糖果，S是總數-N；
如果：S>=N-1必然有解
S<N-1必然無解，?因為我們把糖果當成隔板了，S<N-1則必然這N個糖果，會存在糖果重疊。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;int K;
LL S, N, x;void solve()
{cin >> K;S = N = 0;for(int i = 1; i <= K; i ++){cin >> x;N = max(N, x);S += x;}S -= N;cout << (S >= N - 1 ? "Yes" : "No") << '\n';
}int main()
{cin.tie(0)->sync_with_stdio(false);cout.tie(0);int T = 1;cin >> T;while (T--){solve();}
}

2、高精度運算

基本概念：

高精度，通常是用來處理大的整數，如超過(int、long long)的整數的加減乘除。
通常是用string字符串或數組來儲存這些數，然后模擬手算。

常見類型：

高精度加高精度算法
高精度減高精度算法
高精度乘高精度算法
高精度除低精度算法
高精度循環加
循環高精度乘低精度

高精度+高精度

#include <iostream>
#include <vector>
using namespace std;string add(string str1,string str2){ vector<int> A,B;// 逆序儲存，方便計算 for(int i=str1.size()-1; i>=0; --i) A.push_back(str1[i]-'0');for(int i=str2.size()-1; i>=0; --i) B.push_back(str2[i]-'0');// 相加vector<int> c;int carry=0;for(int i=0; i<A.size()||i<B.size()||carry; ++i){if(i<A.size()) carry+=A[i];if(i<B.size()) carry+=B[i];c.push_back(carry%10);carry/=10;} string str="";for(int i=c.size()-1; i>=0; --i) str+=c[i]+'0'; return str;
}int main(){string num1 = "1534";string num2 = "1534";cout<<add(num1, num2);return 0;
}

高精度-高精度

#include <iostream>
#include <vector>
using namespace std;bool cmp(vector<int> A,vector<int> B){ // true-A>=B.  false->A<B  if(A.size()!=B.size()) return A.size()>B.size(); // 個數不同的情況for(int i=A.size()-1; i>=0; --i){if(A[i]!=B[i]) return A[i]>B[i];}return true; 
}
string sub(string str1, string str2){vector<int> A,B;for(int i=str1.size()-1; i>=0; --i) A.push_back(str1[i]-'0');for(int i=str2.size()-1; i>=0; --i) B.push_back(str2[i]-'0');if(!cmp(A,B)) return "-"+sub(str2,str1); // 如果A<B，則交換位置，并加上負號vector<int> C;int borrow=0; // 結尾的數字for(int i=0; i<A.size(); ++i){borrow=A[i]-borrow; // 當前位的數字if(i<B.size()) borrow-=B[i]; // 天吶，這些都是啥玩意 C.push_back((borrow+10)%10); // 借位or不借位，的結果是多少borrow = borrow<0?1:0;	} while(C.size()!=1&&C[C.size()-1]==0){C.pop_back();}string str="";for(int i=C.size()-1; i>=0; --i){str+=to_string(C[i]);} return str;
}int main(){string num1 = "1000";string num2 = "1999";cout<<sub(num1,num2);return 0;
}

高精度乘高精度算法

#include <iostream>
#include <vector>
using namespace std;
/*高精度-乘法1、算出最多有多少位2、將每個位置的數字，都乘進他該在的位置，記得用+=（模擬乘法3、設置一個借位的數字carry4、輾轉相除，找到他最終的位置5、正常取零 
*/
string mul(string str1,string str2){vector<int> A,B;for(int i=str1.size()-1; i>=0; --i) A.push_back(str1[i]-'0');for(int i=str2.size()-1; i>=0; --i) B.push_back(str2[i]-'0');vector<int> C(A.size()+B.size(),0); for(int i=0; i<A.size(); ++i)for(int j=0; j<B.size(); ++j)C[i+j]+=A[i]*B[j]; // !! 這一步，至關重要 int carry = 0;for(int i=0; i<C.size(); ++i){carry=carry+C[i];C[i]=carry%10;carry/=10; }while(C.size()!=1&&C[C.size()-1]==0) C.pop_back();string str="";for(int i=C.size()-1; i>=0; --i) str+=to_string(C[i]);return str;  
} int main(){string str1="123";string str2="456";cout<<mul(str1,str2);return 0;
}

高精度除于高精度

#include <iostream>
#include <vector>
#include <bits/stdc++.h>
using namespace std;
// 注：寫的過程，需要頭腦清晰
/*本題需要幾個函數除法的實現需要借助（sub減法模擬除法、cmp比較大小 既然是除數了，必然有除數()，也必然存在余數(0or具體的數) 他們都各自用一個vector表示。注意，不要忽略前綴為0的情況用減法模擬除法。 
*/bool cmp(vector<int> v1, vector<int> v2){ // 逆序存入，true代表v1>=v2 , false:v1<v2 if(v1.size()!=v2.size()) return v1.size()>v2.size();for(int i=v1.size()-1;  i>=0; --i)if(v1[i]!=v2[i]) return v1[i]>v2[i];return true; 
}
vector<int> sub(vector<int> v1, vector<int> v2){ // v1>=v2 vector<int> c;int borrow=0; for(int i=0; i<v1.size(); ++i){borrow=v1[i]-borrow; // 借if(i<v2.size()) borrow-=v2[i]; c.push_back((borrow+10)%10);borrow=borrow<0?1:0; }while(c.size()>1&&c.back()==0) c.pop_back();return c;
}string div(string str1, string str2, string& rs){ vector<int> A,B; for(int i=str1.size()-1; i>=0; --i) A.push_back(str1[i]-'0');for(int i=str2.size()-1; i>=0; --i) B.push_back(str2[i]-'0');vector<int> C; // 最后開頭可能會產生0 vector<int> cur; // 存放for(int i=str1.size()-1; i>=0; --i){cur.insert(cur.begin(),A[i]);  while(cur.size()>1&&cur.back()==0) cur.pop_back(); // 放入 int t=0;while(cmp(cur,B)){cur=sub(cur,B);t++;}C.push_back(t);} // 這一步反轉很重要reverse(C.begin(),C.end()); while(C.size()>1&&C.back()==0) C.pop_back();string str=""; for(int i=C.size()-1; i>=0; --i) str+=to_string(C[i]);string r="";for(int i=cur.size()-1; i>=0; --i) r+=to_string(cur[i]);rs=r;return str; 
}int main(){// 高精度除數string s1="1234";string s2="23";string remainer; cout<<div(s1,s2,remainer)<<endl;cout<<remainer<<endl; return 0; 
}

3、快速冪

簡單復習一下，傳送門?:: 快速冪?::

#include <iostream>
using namespace std;
int main(){ // 求3^45 int base=3;int exponent=3;int result=1;while(exponent){if(exponent&1) result*=base;base*=base;  exponent>>=1; }cout<<result;
}

4、最大公約數(gcd)與最小公倍數(lca)

最大公約數，就是兩個數，共有的最大的因數

lcm是最小公倍數 :: 詳細解法 ::

定理：a、b 兩個數的最小公倍數(lcm)乘以它們的最大公約數(gcd)等于 a 和 b 本身的乘積。

如：gcd(a,b) * lcm(a,b)=a*b

#include <iostream>
using namespace std;int gcd(int a,int b){ // 最大公約數 return b!=0?gcd(b,a%b):a;
}int main(){ // 我的天吶，簡直了int num1=10,num2=8; cout<<gcd(num1,num2)<<endl; // 最大公約數cout<<num1*num2/gcd(num1,num2); // 最小公倍數 return 0;
}