/*ReadMe
*only plus & multiply return superInt.
*The others print out.
*the function is_bigger return true whie a>=b,
*function name:
*superInt superPlus(superInt a,superInt b)
*superInt superMultiply(superInt a,superInt b)
*void superMinus(superInt a,superInt b)
*void print(superInt a)
*void print(superInt a)
*bool is_bigger(superInt a,superInt b)
*/
#include<iostream>
#include<cstdio>
#include<climits>
#include<cmath>
#include<set>
#include<cstdlib>
#include<string>
#include<cstring>
#include<algorithm>
#define MAXN (100000+10)
using namespace std;
struct superInt{
int bit;
int ia[MAXN];
};
superInt a,b,add;
void clear(superInt &a)
{
a.bit = 0;
memset(a.ia, 0, sizeof(a.ia));
}
void read(superInt &a)
{
char temp[MAXN];
cin >> temp;
int size = strlen(temp);
a.bit = size;
int tempNum = 0;
for (int i = size; i >= 1; i--)
{
a.ia[i] = temp[tempNum] - 48;
tempNum++;
}
}
void print(superInt a)
{
for (int i = a.bit; i >= 1; i--)
cout << a.ia[i];
cout << endl;
}
bool is_bigger(superInt a, superInt b)
{
if (a.bit>b.bit)
return true;
else if (a.bit == b.bit)
{
if (a.ia[a.bit] >= b.ia[b.bit])
return true;
}
else
return false;
}
superInt superPlus(superInt a,superInt b)
{
int size = max(a.bit,b.bit);
superInt final;
for(int i=1;i<=size;i++)
{
int temp=a.ia[i]+b.ia[i]+final.ia[i];
final.ia[i]=temp%10;
final.ia[i+1]+=temp/10;
}
if(final.ia[size+1]!=0)
final.bit=size+1;
else
final.bit=size;
return final;
}
void superMinus(superInt a, superInt b)
{
if (is_bigger(a, b) == false)//a is smaller
{
cout << "-";
superInt temp = b;
for (int i = 1; i <= temp.bit; i++)
{
if (temp.ia[i]<a.ia[i])
{
temp.ia[i + 1]--;
temp.ia[i] += 10;
}
temp.ia[i] -= a.ia[i];
}
while(temp.ia[temp.bit]==0&&temp.bit>1)
{
temp.bit-=1;
}
print(temp);
}
else
{
superInt temp = a;
for (int i = 1; i <= temp.bit; i++)
{
if (temp.ia[i]<b.ia[i])
{
temp.ia[i + 1]--;
temp.ia[i] += 10;
}
temp.ia[i] -= b.ia[i];
}
while(temp.ia[temp.bit]==0&&temp.bit>1)
{
temp.bit-=1;
}
print(temp);
}
return;
}
superInt superMultiply(superInt a, superInt b)//1*1
{
superInt final;
clear(final);
for (int i = 1; i <= b.bit; i++)//
{
int bit=b.ia[i];//bit=1
superInt temp;
clear(temp);
for(int j=1;j<=a.bit;j++)
{
int sd;//sd==number of significant digit
temp.ia[j]+=bit*a.ia[j];
temp.ia[j+1]+=temp.ia[j]/10;
temp.ia[j]%=10;
if(temp.ia[a.bit+1]!=0)
temp.bit=a.bit+1;
sd=temp.bit;
temp.bit+=i;
temp.bit--;
for(int k=0;k<sd;k++)
{
temp.ia[temp.bit-k]=temp.ia[sd-k];
}
}
final=superPlus(final,temp);//ToDo
}
return final;
}
int main()
{
clear(a);
clear(b);
read(a);
read(b);
superInt c;
c=superMultiply(a,b);
print(c);
return 0;
}
乘法有问题……调试抛出sigsegv;
问题应该是final=superPlus(final,temp);//ToDo这一行,但是菜鸟实在不懂为什么
一进superMultiply
就挂了。和superPlus没关系。
RE的原因应该是爆栈了,中间传的值太大了。栈会受不了的。把栈大小改成128M就不RE了。当然,答案也不对。