2024第十五届蓝桥杯大赛软件赛省赛C/C++ 大学 B 组

Ne0inhk

23 Mar 2026 — 26 min read

记录刷题的过程、感悟、题解。
希望能帮到，那些与我一同前行的，来自远方的朋友😉

大纲：

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，比较要原路返回🔙。
（注-其他读者：首先不要被头文件吓到，不懂可是上网查查，用几次就熟悉了）
（注-自己：起初，我也以为无法实现，包括数的大小撑爆了类型，以及printf的运用...最后还好）

#include <bits/stdc++.h> #define ld long double #define int long long using namespace std; signed main(){ int t = 0; int x=0,y=0; while(true){ t++; x+=15; y+=17; if(x%343720==0&&y%233333==0) break; } ld res = sqrtl((ld)x*x+(ld)y*y); res*=2; printf("%.2Lf",res); return 0; }

3、好数

问题描述

一个整数如果按从低位到高位的顺序，奇数位 (个位、百位、万位 ⋯⋯ ) 上的数字是奇数，偶数位 (十位、千位、十万位 ⋯⋯ ) 上的数字是偶数，我们就称之为 “好数”。

给定一个正整数 N，请计算从 1 到 N 一共有多少个好数。

输入格式

一个整数 N。

输出格式

一个整数代表答案。

样例输入 1

样例输出 1

样例输入 2

样例输出 2

样例说明

对于第一个样例，24 以内的好数有 1、3、5、7、9、21、23，一共 7 个。

评测用例规模与约定

对于 10% 的评测用例，1≤N≤100 。

对于 100%的评测用例，1≤N≤10^7 。

其实.....这道题，真的很简单，如果做不出来，只能说，练的少。

其实就是简单的模拟。

当然如果期间你用reverse反转的话，一定会超时。（先把数字转化为字符串，然后将字符串反转一下，奇数位，必须是偶数；偶数位，必须是奇数。）

解法

这个解法，是我在重复作本题4次之后，打磨出来的，最顺手与合理的写法。
自我感觉：硬是把暴力枚举题，做出模拟题的味道。
在下方，我又给出网上一哥们写的，不错的题解

#include <iostream> using namespace std; // 我觉得，这次我的好数，写的非常优美，一会可以改进一下 int main(){ int n; cin>>n; int cnt = 0; for(int i=1; i<=n; ++i){ int number = i; // 偶数位 为 偶数，奇数位 为奇数。 // 所以巧妙运用place int place = 0; while(number){ int num = number%10; place++; if(place%2!=0&&num%2==0) break; // 奇数位-要为奇数，否则本数不符合，直接跳过 else if(place%2==0&&num%2!=0) break; // 偶数位-要为偶数，否则错了 number/=10; } if(number==0) cnt++; } cout<<cnt<<endl; return 0; }

其他方式

这是我在网上看的一哥们写的，只能说分支被他玩明白了😇

#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 格式表示出来的值。

样例输入

样例输出

样例说明

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

评测用例规模与约定

对于 50% 的评测用例：1≤n≤10,1≤ 将 d 视为字符串时的长度 ≤15。

对于 100% 的评测用例：1≤n≤1000,1≤ 将 d 视为字符串时的长度 ≤1024；保证 d 是小数，即包含小数点。

哎，被这道题目给骗了😇，第一眼看上去，我还以为是快速幂呢。

其实本题本质上，就是一道高精度题目。

在蓝桥杯中，高精度是一个高频考点，我在最下部，高精度各种计算的模板。 ::传送门::

本题，实际上就是，不断乘以2，当然啦，要用高精度的乘法模版乘。循环n次

当然，要先记录一下数点的位置，然后减去。

#include <iostream> #include <vector> #include <algorithm> using namespace std; vector<int> a,b; // 乘法 void multiply(){ 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 += c[i]; c[i]=carry%10; carry/=10; } for(int i=c.size()-1; i>0; --i){ if(c[i]==0) c.pop_back(); else break; } a = c; } int main(){ // 基础处理： int n; string str; cin>>n>>str; reverse(str.begin(),str.end()); int pla = 0; for(int i=0; i<str.size(); ++i){ if(str[i]!='.') a.push_back(str[i]-'0'); else pla=i; } b.push_back(2); // 首先进行乘法运算： for(int i = 0; i<n; ++i){ multiply(); } // 加法： vector<int> res; for(int i=pla; i<a.size(); ++i) res.push_back(a[i]); if(a[pla-1]>=5){ int carry = 1; for(int i=0; i<res.size(); ++i){ carry+=res[i]; res[i]=carry%10; carry/=10; } if(carry!=0) res.push_back(carry); } for(int i=res.size()-1; i>=0; --i) cout<<res[i]; return 0; }

5、宝石组合

输入格式

第一行包含一个整数 N 表示宝石个数。

第二行包含 N 个整数表示 N 个宝石的 “闪亮度”。

输出格式

输出一行包含三个整数表示满足条件的三枚宝石的 “闪亮度”。

样例输入

样例输出

评测用例规模与约定

对于 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)

再看接下来的解法时，你需要掌握两个知识点
1、明白最大公约数与最小公倍数的底层逻辑
2、知晓中国剩余定理(不清楚的话，下方有讲解)

:: 具体的推导方法 ::

当你把公式推导出来之后。

首先在输入的时候，推导出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。

样例输入

样例输出

样例说明

行进路径如图 1 所示。

评测用例规模与约定

对于 80% 的评测用例：1≤N≤5 。

对于 100% 的评测用例：1≤N≤10,1≤K≤10 。

DFS千篇一律，😇😉，好像都是这个模版耶，稍稍总结一下！嘿嘿(～￣▽￣)～
在此解释一下，什么是字典序最小！从第一位开始比较ASCII码值。不用在意长度
如“aaaa”字典序小于“ab”

#include <iostream> #include <vector> using namespace std; // 初始变量 const int N = 15; int n,k; vector<vector<int>> matrix(N,vector<int>(N,0)); bool visited[N][N]; bool square[N][N][N][N]; int dir[8][2]={-1,0,-1,1,0,1,1,1,1,0,1,-1,0,-1,-1,-1}; // 字典序最小？ // 结束条件？如何代表结束？ vector<int> res; int flag = 0; bool dfs(int X, int Y){ if(X==n-1&&Y==n-1&&flag==n*n-1) return true; // 第四个条件 for(int i=0; i<8; ++i){ // 这个是记忆化搜索的呢 int x = X+dir[i][0], y = Y+dir[i][1]; if(x<0||x>=n||y<0||y>=n||visited[x][y]) continue; // 基本项+第三个条件 if((flag+1)%k!=matrix[x][y]) continue; // 第二个条件 if(square[X+dir[i][0]][Y][X][Y+dir[i][1]]) continue; // 第四个条件 // 回溯 visited[x][y]=true; res.push_back(i); flag++; if(i==1||i==3||i==5||i==7){ square[X][Y][x][y]=true; square[x][y][X][Y]=true; } if(dfs(x,y)) return true; if(i==1||i==3||i==5||i==7){ square[X][Y][x][y]=false; square[x][y][X][Y]=false; } flag--; res.pop_back(); visited[x][y]=false; } return false; } int main(){ cin>>n>>k; // 存 for(int i=0; i<n; ++i){ for(int j=0; j<n; ++j){ cin>>matrix[i][j]; } } // dfs flag = 0; visited[0][0]= true; if(dfs(0,0)){ for(int i=0; i<res.size(); ++i) cout<<res[i]; }else cout<<-1<<endl; 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。

输出格式

输出共一行，一个非负整数，表示两个队伍力量值之和的最小差距。

样例输入

样例输出

样例说明

其中一种最优选择方式：

队伍 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字符串或数组来储存这些数，然后模拟手算。

常见类型：

高精度加高精度算法
高精度减高精度算法
高精度乘高精度算法
高精度除低精度算法
高精度循环加
循环高精度乘低精度

高精度+高精度

在做这道题目的时候，需注意细节：“进位问题-carry”，溢出。

#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; 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; 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、设置一个借位的数字carry 4、辗转相除，找到他最终的位置 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; 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; }

高精度除于高精度

1、本题的算法中，若存在前导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; for(int i=C.size()-1; i>=0; --i) str+=to_string(C[i]); string; 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; }