高精度算法
作者：blue
时间：2024.9
1.高精度加法（整数部分模板）
#include <iostream>
#include <string>
using namespace std;
int a1[1000],a2[1000],ans[1000];
int main()
{
string s1,s2;
cin>>s1>>s2;//字符串存放大数
//逆序存放在数组中
for(int i=0;i<s1.size();i++) a1[s1.size()-i-1]=s1[i]-'0';
for(int i=0;i<s2.size();i++) a2[s2.size()-i-1]=s2[i]-'0';
int len=max(s1.size(),s2.size());
//先相加
for(int i=0;i<len;i++){
ans[i]=a1[i]+a2[i];
}
//后处理进位
for(int i=0;i<len;i++){
ans[i+1]=ans[i+1]+ans[i]/10;
ans[i]=ans[i]%10;
}
//逆序输出先判断len位为不为0(因为最高位可能进位，所以最长到len位)
for(int i=len;i>=0;i--){
if(i==len&&ans[len]==0) continue;
cout<<ans[i];
}
return 0;
}
AI 代码解读
2.高精度减法（整数部分模板）
#include <iostream>
#include <string>
using namespace std;
const int N=1e6+10;
int a1[N],a2[N],ans[N];
int main()
{
string s1,s2;
cin>>s1>>s2;
char flag='+';//符号判断
//判断两个数谁大谁小，大的那个放置在s1,如果交换了位置，就将符号置为'-'
if(s1.size()<s2.size()||s1.size()==s2.size()&&s1<s2){
swap(s1,s2);
flag='-';
}
//倒序存放
for(int i=0;i<s1.size();i++) a1[i]=s1[s1.size()-i-1]-'0';
for(int i=0;i<s2.size();i++) a2[i]=s2[s2.size()-i-1]-'0';
for(int i=0;i<s1.size();i++){
if(a1[i]<a2[i]){
//模拟借位的过程
a1[i]+=10;
a1[i+1]--;
}
ans[i]=a1[i]-a2[i];
}
//注意此处index的值设置为0是有考究的，当是两个相等大数相减的话，那就只用输出1位0
int index=0;//找答案中第一个不为0的位置，为输出做准备
for(int i=s1.size()-1;i>=0;i--){
if(ans[i]>0){
index=i;
break;
}
}
if(flag=='-') cout<<flag;
for(int i=index;i>=0;i--) cout<<ans[i];
return 0;
}
AI 代码解读
3.高精度乘法
#include <iostream>
#include <string>
using namespace std;
const int N=1e8+10;
int a1[N],a2[N],ans[N];
int main()
{
string s1,s2;
cin>>s1>>s2;
//反转两个数
for(int i=0;i<s1.size();i++) a1[i]=s1[s1.size()-i-1]-'0';
for(int i=0;i<s2.size();i++) a2[i]=s2[s2.size()-i-1]-'0';
int len=s1.size()+s2.size();//乘法最终的长度不会长于两个常数长度的和
//模拟乘法过程
for(int i=0;i<s1.size();i++){
for(int j=0;j<s2.size();j++){
ans[i+j]+=a1[i]*a2[j];//注意这里不是赋值语句
ans[i+j+1]+=ans[i+j]/10;//进位
ans[i+j]=ans[i+j]%10;//保留本位
}
}
//消除前导0
int index=0;
for(int i=len;i>=0;i--){
if(ans[i]!=0){
index=i;
break;
}
}
//倒序输出
for(int i=index;i>=0;i--){
cout<<ans[i];
}
return 0;
}
AI 代码解读
4.高精度除法
高精度除以低精度
#include <iostream>
#include <string>
using namespace std;
const int N=1e8+10;
int ans[N],a[N];
long long b;
int main()
{
string s;
long long x=0;//用以承接每次的余数，初始应当为0，因为没有余数，注意这里余数也要开long long 防止余数很大的情况
cin>>s>>b;//输入一个高精度数和一个低精度数
//这里不用倒序存放，因为除法本身就是一个从高位计算到低位的过程
for(int i=0;i<s.size();i++) a[i]=s[i]-'0';
//模拟逐位试商的过程
for(int i=0;i<s.size();i++){
ans[i]=(x*10+a[i])/b;
x=(x*10+a[i])%b;
}
int index=0;
//消除前导0，注意此处，index不能超过被除数的长度
while(ans[index]==0&&index<s.size()) index++;
for(int i=index;i<s.size();i++) cout<<ans[i];
if(index==s.size()) cout<<"0";//如果index等于被除数的长度，那么说明商就为0，要打印0
//cout<<" "<<x;//有需要还可以打印余数
return 0;
}
AI 代码解读
高精度除以高精度
高精度除高精度要用减法模拟除法
#include <iostream>
#include <string>
#include <cstring>
using namespace std;
const int N=1e6+10;
int a[N],b[N],c[N],tmp[N];
void init(int a[]){
string s;
cin>>s;
a[0]=s.size();//a[0]存储字符串的长度
for(int i=1;i<=s.size();i++) a[i]=s[s.size()-i]-'0';//逆序存储
}
void print(int a[]){
if(a[0]==0){
cout<<"0";
return;
}
for(int i=a[0];i>0;i--) cout<<a[i];
return;
}
int compare(int a[],int b[]){
//比较两个数的大小，如果a大返回1，如果b大返回-1，一样大返回0
if(a[0]>b[0]) return 1;
if(a[0]<b[0]) return -1;
for(int i=a[0];i>0;i--){
if(a[i]>b[i]) return 1;
if(a[i]<b[i]) return -1;
}
return 0;
}
void minu(int a[],int b[]){
//高精度减法
for(int i=1;i<=a[0];i++)
{
if(a[i]<b[i]){
a[i]+=10;
a[i+1]--;
}
a[i]=a[i]-b[i];
}
while(a[a[0]]==0&&a[0]>0) a[0]--;//删除前导0
return;
}
void numcpy(int b[],int tmp[],int n){
//
for(int i=1;i<=b[0];i++) tmp[i+n]=b[i];
tmp[0]=b[0]+n;
}
int main()
{
init(a);
init(b);
c[0]=a[0]-b[0]+1;//两位数相除，商最长的长度
if(c[0]<0) c[0]=0;
for(int i=c[0];i>=1;i--){
memset(tmp,0,sizeof(tmp));
numcpy(b,tmp,i-1);//减法模拟除法，扩展减数，和被减数一样长
while(compare(a,tmp)>=0){
//减干净
c[i]++;
minu(a,tmp);
}
}
while(c[c[0]]==0&&c[0]>0) c[0]--;//消去前导0
print(c);
//print(a);//余数
}
AI 代码解读
5.高精度取模
蛐蛐取mod，直接拿下
4.字符串加法【算法赛】 - 蓝桥云课 (lanqiao.cn)
#include <iostream>
#include <string>
#define int long long
using namespace std;
const int mod=1e9+7;
long long long_mod(string a)
{
int ans=0;
for(int i=0;i<a.size();i++){
ans=(ans*10+(a[i]-'0'))%mod;
}
return ans;
}
signed main()
{
string a,b,res;
cin>>a>>b;
res=a+b;
cout<<long_mod(res);
return 0;
}
AI 代码解读
