记录刷题的过程、感悟、题解。
希望能帮到，那些与我一同前行的，来自远方的朋友😉
大纲：
1、握手问题-（解析）-简单组合问题（别人叫她 鸽巢定理）😇，感觉叫高级了
题目：
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 long
using 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 的字典序小于 t
if (t.empty() || res < t) {
// 更新 t 为当前路径 res
t = 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 和数字循环的周期 k
cin >> 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) 开始进行深度优先搜索，步数为 1
dfs(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、设置一个借位的数字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 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;
} 5、gcd与lcm推导
总结：
通过质因数分解和指数分析，我们发现：
- 所有质因数的最小指数相乘，就是三个数的最大公约数（GCD)
- 你在网上列举其他例子也是这样😄，我私下推导过。
借鉴博客：
2、拔河
3、差分具体用法