Miier @ 2022-07-22 09:57:37
#include <stdio.h>
#include <string.h>
typedef struct
{
int num[11000];
int len;
int neg;
}BIGINT;
BIGINT str2int(char* p);
BIGINT add(BIGINT a,BIGINT b);//高精度加法
BIGINT sub(BIGINT a,BIGINT b);//高精度减法
BIGINT mul(BIGINT a,BIGINT b);//高精度乘低精度
int main()
{
char sa[11000],sb[11000];
scanf("%s %s",sa,sb);
BIGINT ia=str2int(sa),ib=str2int(sb);
BIGINT ans=mul(ia,ib);
if(ans.neg) printf("-");
for(int i=ans.len-1;i>=0;i--) printf("%d",ans.num[i]);
}
BIGINT str2int(char* p)
{
BIGINT ans={{0},0,0};
for(int i=strlen(p)-1;i>=0;i--)
{
ans.num[ans.len++]=p[i]-'0';
}
return ans;
}
BIGINT add(BIGINT a,BIGINT b)
{
int len=a.len>b.len?a.len:b.len;
BIGINT ans={{0},len,0};
int temp,carry=0;
for(int i=0;i<len;i++)
{
temp=a.num[i]+b.num[i]+carry;
ans.num[i]=temp%10;
carry=temp/10;
}
if(carry)
{
ans.num[len]=carry;
ans.len=len+1;
}
return ans;
}
BIGINT sub(BIGINT a,BIGINT b)
{
BIGINT ans={{0},a.len>b.len?a.len:b.len,0};
if(a.len<b.len)//确保大数减去小数
{
ans=sub(b,a);
ans.neg=1;
return ans;
}
else if(a.len==b.len)
{
for(int i=a.len-1;i>=0;i--)
{
if(a.num[i]<b.num[i])
{
ans=sub(b,a);
ans.neg=1;
return ans;
}
}
}
int temp,carry=0;
for(int i=0;i<a.len;i++)
{
temp=a.num[i]-b.num[i]-carry;
carry=temp<0?1:0;
ans.num[i]=(temp+10)%10;//借位可能产生负数，加10不影响余数
}
// for(int i=a.len-1;i>=0;i--)//确定相减结果的位数
// {
// if(ans.num[i]!=0)
// {
// ans.len=i+1;
// return ans;
// }
// }
// ans.len=1;
ans.len=a.len>b.len?a.len:b.len;//确定相减的位数，注意初始化ans.len
while(ans.num[ans.len-1]==0&&ans.len>1) ans.len--;
return ans;
}
BIGINT mul(BIGINT a,BIGINT b)
{
BIGINT c={{0},a.len+b.len,0};//a*b的最大长度位a、b的幂次和
int temp=0,carry=0;
for(int i=0;i<a.len;i++)
{
for(int j=0;j<b.len;j++)
{
temp=a.num[i]*b.num[j]+carry+c.num[i+j];
c.num[i+j]=temp%10;
carry=temp/10;
}
c.num[i+b.len]=carry;
}
c.len=a.len+b.len;
while(c.num[c.len-1]==0&&c.len>1) c.len--;
return c;
}
by tin_ingot @ 2022-07-22 10:34:33
@Miier 高精乘高精
by Miier @ 2022-07-22 10:43:07
@滑稽人 前面注释写错了，后面是高精度乘高精度的算法。大佬有空的话能帮忙看看吗，感谢:)
by tin_ingot @ 2022-07-22 10:57:14
@Miier 精简了一下
#include<stdio.h>
#include<string.h>
#define N 50010
char x[N],y[N];
int a[N],b[N],c[N];
int main()
{
scanf("%s%s",x,y);
a[0]=strlen(x);b[0]=strlen(y);
for(int i=1;i<=a[0];i++) a[i]=x[a[0]-i]-'0';
for(int i=1;i<=b[0];i++) b[i]=y[b[0]-i]-'0';
for(int i=1;i<=a[0];i++)
for(int j=1;j<=b[0];j++)
c[i+j-1]+=a[i]*b[j];
int len=a[0]+b[0];
for(int i=1;i<=len-1;i++)
if(c[i]>9)
{
c[i+1]+=c[i]/10;
c[i]%=10;
}
while(c[len]==0&&len>1) len--;
for(int i=len;i>=1;i--) printf("%d",c[i]);
return 0;
} by Miier @ 2022-07-22 11:11:34
@滑稽人 多谢大佬的代码，看了你的代码之后我还是不明白自己的代码错在哪里了:( 大佬可否看看我的代码，多谢
by tin_ingot @ 2022-07-22 11:13:46
@Miier 那我的看懂了吗？
by tin_ingot @ 2022-07-22 11:35:18
@Miier 改好了：
#include <stdio.h>
#include <string.h>
#define N 4000+10
typedef struct
{
int num[N],len;
} lll;
lll to_int(char *p)
{
lll ans={{0},0};
for(int i=strlen(p)-1; i>=0; i--)
{
ans.num[ans.len++]=p[i]-'0';
}
return ans;
}
void mul(lll a,lll b)
{
lll c= {{0},N};
for(int i=0; i<a.len; i++)
{
for(int j=0; j<b.len; j++)
{
c.num[i+j]+=a.num[i]*b.num[j];
}
}
for(int i=0; i<N; i++)
{
c.num[i+1]+=c.num[i]/10;
c.num[i]%=10;
}
c.len=N-1;
while(c.num[c.len]==0&&c.len>0) c.len--;
for(int i=c.len;i>=0;i--) putchar(c.num[i]^48);
}
int main()
{
char sa[11000],sb[11000];
scanf("%s%s",sa,sb);
lll ia=to_int(sa);
lll ib=to_int(sb);
mul(ia,ib);
}by Miier @ 2022-07-22 18:17:17
@滑稽人 结合大佬的代码我终于搞明白了！我原来的代码出错的原因是每次进第一层循环carry没有重新设置为0.多谢大佬解答:)
by LeeJC @ 2022-10-28 18:23:38
#include <stdio.h>
#include <string.h>
int main()
{
char s[2001],ss[2001];
scanf("%s %s",s,ss);
int i,j,a[2002],b[2002],c[500001];
a[0]=strlen(s);
b[0]=strlen(ss);
for(i=1;i<=a[0];i++)
a[i]=s[a[0]-i]-'0';
for(i=1;i<=b[0];i++)
b[i]=ss[b[0]-i]-'0';
for(i=1;i<=a[0];i++)
for(j=1;j<=b[0];j++)
c[i+j-1]=a[i]*b[j];
for(i=1;i<a[0]+b[0];i++)
if(c[i]>9)
{
c[i+1]+=c[i]/10;
c[i]%=10;
}
int len=a[0]+b[0];
while(c[len]==0&&len>1)
len--;
for(i=len;i>0;i--)
printf("%d",c[i]);
return 0;
}@滑稽人 我靠大佬，一模一样啊，就AC了一个点
by tin_ingot @ 2022-10-28 18:38:39
@LeeJC 首先，你的代码要把数组开在外面，不然main函数可能会爆内存：
#include <stdio.h>
#include <string.h>
char s[2001],ss[2001];
int i,j,a[2002],b[2002],c[500001];
int main()
{
scanf("%s %s",s,ss);
a[0]=strlen(s);
b[0]=strlen(ss);
for(i=1;i<=a[0];i++)
a[i]=s[a[0]-i]-'0';
for(i=1;i<=b[0];i++)
b[i]=ss[b[0]-i]-'0';
for(i=1;i<=a[0];i++)
for(j=1;j<=b[0];j++)
c[i+j-1]=a[i]*b[j];
for(i=1;i<a[0]+b[0];i++)
if(c[i]>9)
{
c[i+1]+=c[i]/10;
c[i]%=10;
}
int len=a[0]+b[0];
while(c[len]==0&&len>1)
len--;
for(i=len;i>0;i--)
printf("%d",c[i]);
return 0;
}by tin_ingot @ 2022-10-28 18:55:41
@LeeJC
#include <stdio.h>
#include <string.h>
char s1[2001],s2[2001];
int i,j,a[2002],b[2002],c[500001];
int main()
{
scanf("%s %s",s1,s2);
a[0]=strlen(s1);
b[0]=strlen(s2);
for(i=1;i<=a[0];i++)
a[i]=s1[a[0]-i]-'0';
for(i=1;i<=b[0];i++)
b[i]=s2[b[0]-i]-'0';
for(i=1;i<=a[0];i++)
for(j=1;j<=b[0];j++)
// c[i+j-1]=a[i]*b[j];
// 把=改成+=
c[i+j-1]+=a[i]*b[j];
int len=a[0]+b[0];
for(i=1;i<len;i++)
if(c[i]>9)
{
c[i+1]+=c[i]/10;
c[i]%=10;
}
while(c[len]==0&&len>1) len--;
for(i=len;i>0;i--) printf("%d",c[i]);
return 0;
}