#include<cstdio>
#include<iostream>
#include<string>
#include<cstdlib>
#include<cstring>
using namespace std;
inline int toint(char c)
{
return c - '0';
}
inline char tochar(int c)
{
return '0' + c;
}
void mult(string a, string b,int m, int n,int w[][20001],int num)
{
int k,buff,t;
for(int j = n-1;j>=0;j--)
{
k = 0;
for(int i = m-1;i>=0;i--)
{
t = toint(a[i])*toint(b[j]) + w[num][i+j+1] + k;
buff = t%10;
k = t/10;
w[num][i+j+1] = buff;
}
w[num][j] = k;
}
for (int i = 0;i<m+n;i++)
cout << w[num][i];
cout << endl;
}
int main(int argc,char** argv){
string str_num;
int num,m,n;
getline(cin,str_num);
num = atoi(str_num.c_str());
string s1,s2;
static int w[1001][20001] = {{0}};
//static int a[1001][10001] = {{0}};
//static int b[1001][10001] = {{0}};
int idx = 0;
while(idx < num) {
getline(cin,s1,' ');
getline(cin,s2);
m = s1.size();
n = s2.size();
mult(s1,s2,m,n,w,idx);
idx++;
}
return 1;
}
I don't get it. Why is this too slow for even TMUL ? I thought this is a algorithm with \theta(m*n) complexity ? Isn't it ?