MMT9. 大数乘法
描述
实现大数乘法，输入是两个字符串如输入描述
一行，两个非负整数n1,n2，保证|n1|+|n2|<10000，其中|n|是n作为字符串的长度输出描述
输出n1*n2的结果示例1
输入:
340282366920938463463374607431768211456 340282366920938463463374607431768211456
输出:
115792089237316195423570985008687907853269984665640564039457584007913129639936
C++ 解法, 执行用时: 7ms, 内存消耗: 780KB, 提交时间: 2020-10-31
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=3000,B=10000;
int A[100100];
struct number {
int n;
int a[N];
void clear() { n=0;memset(a,0,sizeof a);}
void work() { while (n>1 && !a[n]) n--;}
number read() {
memset(A,0,sizeof A);
clear();
char ch=getchar();
while (ch<'0' || '9'<ch) ch=getchar();
while ('0'<=ch && ch<='9') A[++n]=ch-'0',ch=getchar();
for (int i=1;i+i<=n;i++) swap(A[i],A[n-i+1]);
for (int i=1;i<=n;i+=4) {
int j=(i+3)/4;
a[j]=A[i+3]*1000+A[i+2]*100+A[i+1]*10+A[i];
}
n=(n+3)/4;
return *this;
}
number write() const {
printf("%d",a[n]);
for (int i=n-1;i>0;i--) printf("%04d",a[i]);
return *this;
}
bool operator < (const number &nt) const {
if (n<nt.n) return 1;
if (n>nt.n) return 0;
for (int i=n;i;i--)
if (a[i]!=nt.a[i]) return a[i]<nt.a[i];
return 0;
}
bool operator > (const number &nt) const {
return nt<*this;
}
bool operator != (const number &nt) const {
return *this<nt || nt<*this;
}
bool operator == (const number &nt) const {
return !(*this!=nt);
}
number operator = (const int &nt) {
n=0;
int x=nt;
while (x) {
a[++n]=x%B;
x/=B;
}
return *this;
}
number operator = (const ll &nt) {
n=0;
ll x=nt;
while (x) {
a[++n]=x%B;
x/=B;
}
return *this;
}
number operator + (const number &nt) const {
number tmp;
tmp.clear();
tmp.n=max(n,nt.n)+1;
for (int i=1;i<=tmp.n;i++) {
tmp.a[i]+=a[i]+nt.a[i];
tmp.a[i+1]+=tmp.a[i]/B;
tmp.a[i]%=B;
}
tmp.work();
return tmp;
}
number operator - (const number &nt) const {
number tmp;
tmp.clear();
tmp.n=n;
int x=0;
for (int i=1;i<=tmp.n;i++) {
x+=a[i]-nt.a[i];
if (x<0) tmp.a[i]=x+B,x=-1;
else tmp.a[i]=x,x=0;
}
tmp.work();
return tmp;
}
number operator * (const number &nt) const {
number tmp;
tmp.clear();
tmp.n=n+nt.n;
for (int i=1;i<=n;i++)
for (int j=1;j<=nt.n;j++)
{
tmp.a[i+j-1]+=a[i]*nt.a[j];
tmp.a[i+j]+=tmp.a[i+j-1]/B;
tmp.a[i+j-1]%=B;
}
for (int i=1;i<=tmp.n;i++) {
tmp.a[i+1]+=tmp.a[i]/B;
tmp.a[i]%=B;
}
tmp.work();
return tmp;
}
number operator / (const int &nt) const {
number tmp;
tmp.clear();
tmp.n=n;
ll x=0;
for (int i=n;i;i--) {
x=x*B+a[i];
tmp.a[i]=x/nt;
x%=nt;
}
tmp.work();
return tmp;
}
int operator % (const int &nt) const {
int tmp=0;
for (int i=1;i<=n;i++) tmp=((ll) tmp*B+a[i])%nt;
return tmp;
}
number operator += (const number &nt) { return *this=*this+nt;}
number operator -= (const number &nt) { return *this=*this-nt;}
number operator *= (const number &nt) { return *this=*this*nt;}
number operator /= (const int &nt) { return *this=*this/nt;}
};
number a,b;
number gcd(number a,number b) {
int na=0,nb=0;
while (!(a.a[1]&1)) a/=2,na++;
while (!(b.a[1]&1)) b/=2,nb++;
int x=min(na,nb);
while (a!=b) {
if (a<b) swap(a,b);
a=a-b;
while (!(a.a[1]&1)) a/=2;
}
number t;
t=2;
while (x--) a*=t;
return a;
}
int main() {
a.read();
b.read();
(a*b).write();
}
C++ 解法, 执行用时: 7ms, 内存消耗: 888KB, 提交时间: 2020-08-14
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=3000,B=10000;
int A[100100];
struct number {
int n;
int a[N];
void clear() { n=0;memset(a,0,sizeof a);}
void work() { while (n>1 && !a[n]) n--;}
number read() {
memset(A,0,sizeof A);
clear();
char ch=getchar();
while (ch<'0' || '9'<ch) ch=getchar();
while ('0'<=ch && ch<='9') A[++n]=ch-'0',ch=getchar();
for (int i=1;i+i<=n;i++) swap(A[i],A[n-i+1]);
for (int i=1;i<=n;i+=4) {
int j=(i+3)/4;
a[j]=A[i+3]*1000+A[i+2]*100+A[i+1]*10+A[i];
}
n=(n+3)/4;
return *this;
}
number write() const {
printf("%d",a[n]);
for (int i=n-1;i>0;i--) printf("%04d",a[i]);
return *this;
}
bool operator < (const number &nt) const {
if (n<nt.n) return 1;
if (n>nt.n) return 0;
for (int i=n;i;i--)
if (a[i]!=nt.a[i]) return a[i]<nt.a[i];
return 0;
}
bool operator > (const number &nt) const {
return nt<*this;
}
bool operator != (const number &nt) const {
return *this<nt || nt<*this;
}
bool operator == (const number &nt) const {
return !(*this!=nt);
}
number operator = (const int &nt) {
n=0;
int x=nt;
while (x) {
a[++n]=x%B;
x/=B;
}
return *this;
}
number operator = (const ll &nt) {
n=0;
ll x=nt;
while (x) {
a[++n]=x%B;
x/=B;
}
return *this;
}
number operator + (const number &nt) const {
number tmp;
tmp.clear();
tmp.n=max(n,nt.n)+1;
for (int i=1;i<=tmp.n;i++) {
tmp.a[i]+=a[i]+nt.a[i];
tmp.a[i+1]+=tmp.a[i]/B;
tmp.a[i]%=B;
}
tmp.work();
return tmp;
}
number operator - (const number &nt) const {
number tmp;
tmp.clear();
tmp.n=n;
int x=0;
for (int i=1;i<=tmp.n;i++) {
x+=a[i]-nt.a[i];
if (x<0) tmp.a[i]=x+B,x=-1;
else tmp.a[i]=x,x=0;
}
tmp.work();
return tmp;
}
number operator * (const number &nt) const {
number tmp;
tmp.clear();
tmp.n=n+nt.n;
for (int i=1;i<=n;i++)
for (int j=1;j<=nt.n;j++)
{
tmp.a[i+j-1]+=a[i]*nt.a[j];
tmp.a[i+j]+=tmp.a[i+j-1]/B;
tmp.a[i+j-1]%=B;
}
for (int i=1;i<=tmp.n;i++) {
tmp.a[i+1]+=tmp.a[i]/B;
tmp.a[i]%=B;
}
tmp.work();
return tmp;
}
number operator / (const int &nt) const {
number tmp;
tmp.clear();
tmp.n=n;
ll x=0;
for (int i=n;i;i--) {
x=x*B+a[i];
tmp.a[i]=x/nt;
x%=nt;
}
tmp.work();
return tmp;
}
int operator % (const int &nt) const {
int tmp=0;
for (int i=1;i<=n;i++) tmp=((ll) tmp*B+a[i])%nt;
return tmp;
}
number operator += (const number &nt) { return *this=*this+nt;}
number operator -= (const number &nt) { return *this=*this-nt;}
number operator *= (const number &nt) { return *this=*this*nt;}
number operator /= (const int &nt) { return *this=*this/nt;}
};
number a,b;
number gcd(number a,number b) {
int na=0,nb=0;
while (!(a.a[1]&1)) a/=2,na++;
while (!(b.a[1]&1)) b/=2,nb++;
int x=min(na,nb);
while (a!=b) {
if (a<b) swap(a,b);
a=a-b;
while (!(a.a[1]&1)) a/=2;
}
number t;
t=2;
while (x--) a*=t;
return a;
}
int main() {
a.read();
b.read();
(a*b).write();
}
C++ 解法, 执行用时: 8ms, 内存消耗: 760KB, 提交时间: 2020-10-31
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=3000,B=10000;
int A[100100];
struct number {
int n;
int a[N];
void clear() { n=0;memset(a,0,sizeof a);}
void work() { while (n>1 && !a[n]) n--;}
number read() {
memset(A,0,sizeof A);
clear();
char ch=getchar();
while (ch<'0' || '9'<ch) ch=getchar();
while ('0'<=ch && ch<='9') A[++n]=ch-'0',ch=getchar();
for (int i=1;i+i<=n;i++) swap(A[i],A[n-i+1]);
for (int i=1;i<=n;i+=4) {
int j=(i+3)/4;
a[j]=A[i+3]*1000+A[i+2]*100+A[i+1]*10+A[i];
}
n=(n+3)/4;
return *this;
}
number write() const {
printf("%d",a[n]);
for (int i=n-1;i>0;i--) printf("%04d",a[i]);
return *this;
}
bool operator < (const number &nt) const {
if (n<nt.n) return 1;
if (n>nt.n) return 0;
for (int i=n;i;i--)
if (a[i]!=nt.a[i]) return a[i]<nt.a[i];
return 0;
}
bool operator > (const number &nt) const {
return nt<*this;
}
bool operator != (const number &nt) const {
return *this<nt || nt<*this;
}
bool operator == (const number &nt) const {
return !(*this!=nt);
}
number operator = (const int &nt) {
n=0;
int x=nt;
while (x) {
a[++n]=x%B;
x/=B;
}
return *this;
}
number operator = (const ll &nt) {
n=0;
ll x=nt;
while (x) {
a[++n]=x%B;
x/=B;
}
return *this;
}
number operator + (const number &nt) const {
number tmp;
tmp.clear();
tmp.n=max(n,nt.n)+1;
for (int i=1;i<=tmp.n;i++) {
tmp.a[i]+=a[i]+nt.a[i];
tmp.a[i+1]+=tmp.a[i]/B;
tmp.a[i]%=B;
}
tmp.work();
return tmp;
}
number operator - (const number &nt) const {
number tmp;
tmp.clear();
tmp.n=n;
int x=0;
for (int i=1;i<=tmp.n;i++) {
x+=a[i]-nt.a[i];
if (x<0) tmp.a[i]=x+B,x=-1;
else tmp.a[i]=x,x=0;
}
tmp.work();
return tmp;
}
number operator * (const number &nt) const {
number tmp;
tmp.clear();
tmp.n=n+nt.n;
for (int i=1;i<=n;i++)
for (int j=1;j<=nt.n;j++)
{
tmp.a[i+j-1]+=a[i]*nt.a[j];
tmp.a[i+j]+=tmp.a[i+j-1]/B;
tmp.a[i+j-1]%=B;
}
for (int i=1;i<=tmp.n;i++) {
tmp.a[i+1]+=tmp.a[i]/B;
tmp.a[i]%=B;
}
tmp.work();
return tmp;
}
number operator / (const int &nt) const {
number tmp;
tmp.clear();
tmp.n=n;
ll x=0;
for (int i=n;i;i--) {
x=x*B+a[i];
tmp.a[i]=x/nt;
x%=nt;
}
tmp.work();
return tmp;
}
int operator % (const int &nt) const {
int tmp=0;
for (int i=1;i<=n;i++) tmp=((ll) tmp*B+a[i])%nt;
return tmp;
}
number operator += (const number &nt) { return *this=*this+nt;}
number operator -= (const number &nt) { return *this=*this-nt;}
number operator *= (const number &nt) { return *this=*this*nt;}
number operator /= (const int &nt) { return *this=*this/nt;}
};
number a,b;
number gcd(number a,number b) {
int na=0,nb=0;
while (!(a.a[1]&1)) a/=2,na++;
while (!(b.a[1]&1)) b/=2,nb++;
int x=min(na,nb);
while (a!=b) {
if (a<b) swap(a,b);
a=a-b;
while (!(a.a[1]&1)) a/=2;
}
number t;
t=2;
while (x--) a*=t;
return a;
}
int main() {
a.read();
b.read();
(a*b).write();
}
C++ 解法, 执行用时: 8ms, 内存消耗: 872KB, 提交时间: 2020-07-28
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=3000,B=10000;
int A[100100];
struct number {
int n;
int a[N];
void clear() { n=0;memset(a,0,sizeof a);}
void work() { while (n>1 && !a[n]) n--;}
number read() {
memset(A,0,sizeof A);
clear();
char ch=getchar();
while (ch<'0' || '9'<ch) ch=getchar();
while ('0'<=ch && ch<='9') A[++n]=ch-'0',ch=getchar();
for (int i=1;i+i<=n;i++) swap(A[i],A[n-i+1]);
for (int i=1;i<=n;i+=4) {
int j=(i+3)/4;
a[j]=A[i+3]*1000+A[i+2]*100+A[i+1]*10+A[i];
}
n=(n+3)/4;
return *this;
}
number write() const {
printf("%d",a[n]);
for (int i=n-1;i>0;i--) printf("%04d",a[i]);
return *this;
}
bool operator < (const number &nt) const {
if (n<nt.n) return 1;
if (n>nt.n) return 0;
for (int i=n;i;i--)
if (a[i]!=nt.a[i]) return a[i]<nt.a[i];
return 0;
}
bool operator > (const number &nt) const {
return nt<*this;
}
bool operator != (const number &nt) const {
return *this<nt || nt<*this;
}
bool operator == (const number &nt) const {
return !(*this!=nt);
}
number operator = (const int &nt) {
n=0;
int x=nt;
while (x) {
a[++n]=x%B;
x/=B;
}
return *this;
}
number operator = (const ll &nt) {
n=0;
ll x=nt;
while (x) {
a[++n]=x%B;
x/=B;
}
return *this;
}
number operator + (const number &nt) const {
number tmp;
tmp.clear();
tmp.n=max(n,nt.n)+1;
for (int i=1;i<=tmp.n;i++) {
tmp.a[i]+=a[i]+nt.a[i];
tmp.a[i+1]+=tmp.a[i]/B;
tmp.a[i]%=B;
}
tmp.work();
return tmp;
}
number operator - (const number &nt) const {
number tmp;
tmp.clear();
tmp.n=n;
int x=0;
for (int i=1;i<=tmp.n;i++) {
x+=a[i]-nt.a[i];
if (x<0) tmp.a[i]=x+B,x=-1;
else tmp.a[i]=x,x=0;
}
tmp.work();
return tmp;
}
number operator * (const number &nt) const {
number tmp;
tmp.clear();
tmp.n=n+nt.n;
for (int i=1;i<=n;i++)
for (int j=1;j<=nt.n;j++)
{
tmp.a[i+j-1]+=a[i]*nt.a[j];
tmp.a[i+j]+=tmp.a[i+j-1]/B;
tmp.a[i+j-1]%=B;
}
for (int i=1;i<=tmp.n;i++) {
tmp.a[i+1]+=tmp.a[i]/B;
tmp.a[i]%=B;
}
tmp.work();
return tmp;
}
number operator / (const int &nt) const {
number tmp;
tmp.clear();
tmp.n=n;
ll x=0;
for (int i=n;i;i--) {
x=x*B+a[i];
tmp.a[i]=x/nt;
x%=nt;
}
tmp.work();
return tmp;
}
int operator % (const int &nt) const {
int tmp=0;
for (int i=1;i<=n;i++) tmp=((ll) tmp*B+a[i])%nt;
return tmp;
}
number operator += (const number &nt) { return *this=*this+nt;}
number operator -= (const number &nt) { return *this=*this-nt;}
number operator *= (const number &nt) { return *this=*this*nt;}
number operator /= (const int &nt) { return *this=*this/nt;}
};
number a,b;
number gcd(number a,number b) {
int na=0,nb=0;
while (!(a.a[1]&1)) a/=2,na++;
while (!(b.a[1]&1)) b/=2,nb++;
int x=min(na,nb);
while (a!=b) {
if (a<b) swap(a,b);
a=a-b;
while (!(a.a[1]&1)) a/=2;
}
number t;
t=2;
while (x--) a*=t;
return a;
}
int main() {
a.read();
b.read();
(a*b).write();
}
C++ 解法, 执行用时: 8ms, 内存消耗: 884KB, 提交时间: 2020-11-01
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=3000,B=10000;
int A[100100];
struct number {
int n;
int a[N];
void clear() { n=0;memset(a,0,sizeof a);}
void work() { while (n>1 && !a[n]) n--;}
number read() {
memset(A,0,sizeof A);
clear();
char ch=getchar();
while (ch<'0' || '9'<ch) ch=getchar();
while ('0'<=ch && ch<='9') A[++n]=ch-'0',ch=getchar();
for (int i=1;i+i<=n;i++) swap(A[i],A[n-i+1]);
for (int i=1;i<=n;i+=4) {
int j=(i+3)/4;
a[j]=A[i+3]*1000+A[i+2]*100+A[i+1]*10+A[i];
}
n=(n+3)/4;
return *this;
}
number write() const {
printf("%d",a[n]);
for (int i=n-1;i>0;i--) printf("%04d",a[i]);
return *this;
}
bool operator < (const number &nt) const {
if (n<nt.n) return 1;
if (n>nt.n) return 0;
for (int i=n;i;i--)
if (a[i]!=nt.a[i]) return a[i]<nt.a[i];
return 0;
}
bool operator > (const number &nt) const {
return nt<*this;
}
bool operator != (const number &nt) const {
return *this<nt || nt<*this;
}
bool operator == (const number &nt) const {
return !(*this!=nt);
}
number operator = (const int &nt) {
n=0;
int x=nt;
while (x) {
a[++n]=x%B;
x/=B;
}
return *this;
}
number operator = (const ll &nt) {
n=0;
ll x=nt;
while (x) {
a[++n]=x%B;
x/=B;
}
return *this;
}
number operator + (const number &nt) const {
number tmp;
tmp.clear();
tmp.n=max(n,nt.n)+1;
for (int i=1;i<=tmp.n;i++) {
tmp.a[i]+=a[i]+nt.a[i];
tmp.a[i+1]+=tmp.a[i]/B;
tmp.a[i]%=B;
}
tmp.work();
return tmp;
}
number operator - (const number &nt) const {
number tmp;
tmp.clear();
tmp.n=n;
int x=0;
for (int i=1;i<=tmp.n;i++) {
x+=a[i]-nt.a[i];
if (x<0) tmp.a[i]=x+B,x=-1;
else tmp.a[i]=x,x=0;
}
tmp.work();
return tmp;
}
number operator * (const number &nt) const {
number tmp;
tmp.clear();
tmp.n=n+nt.n;
for (int i=1;i<=n;i++)
for (int j=1;j<=nt.n;j++)
{
tmp.a[i+j-1]+=a[i]*nt.a[j];
tmp.a[i+j]+=tmp.a[i+j-1]/B;
tmp.a[i+j-1]%=B;
}
for (int i=1;i<=tmp.n;i++) {
tmp.a[i+1]+=tmp.a[i]/B;
tmp.a[i]%=B;
}
tmp.work();
return tmp;
}
number operator / (const int &nt) const {
number tmp;
tmp.clear();
tmp.n=n;
ll x=0;
for (int i=n;i;i--) {
x=x*B+a[i];
tmp.a[i]=x/nt;
x%=nt;
}
tmp.work();
return tmp;
}
int operator % (const int &nt) const {
int tmp=0;
for (int i=1;i<=n;i++) tmp=((ll) tmp*B+a[i])%nt;
return tmp;
}
number operator += (const number &nt) { return *this=*this+nt;}
number operator -= (const number &nt) { return *this=*this-nt;}
number operator *= (const number &nt) { return *this=*this*nt;}
number operator /= (const int &nt) { return *this=*this/nt;}
};
number a,b;
number gcd(number a,number b) {
int na=0,nb=0;
while (!(a.a[1]&1)) a/=2,na++;
while (!(b.a[1]&1)) b/=2,nb++;
int x=min(na,nb);
while (a!=b) {
if (a<b) swap(a,b);
a=a-b;
while (!(a.a[1]&1)) a/=2;
}
number t;
t=2;
while (x--) a*=t;
return a;
}
int main() {
a.read();
b.read();
(a*b).write();
}