超时

P1303 A*B Problem

封癫 @ 2016-10-29 20:55:18

#include<iostream>
#include<cstring>
using namespace std;
int main()
{
    string a1,b1;
    int a[100]={0},b[100]={0},c[300]={0};
    int lena,lenb,lenc,x;
    //各种定义 
    cin>>a1;
    cin>>b1;
    lena=a1.size();
    lenb=b1.size();
    for(int i=0;i<=lena-1;++i)
    {a[lena-i]=a1[i]-48;}
    for(int i=0;i<=lenb-1;++i)
    {b[lenb-i]=b1[i]-48;}
    //倒序存储 
    for(int i=1;i<=lena;++i)
    {
        x=0;
        for(int j=1;j<=lenb;j++)
        {
            c[i+j-1]=a[i]*b[j]+x+c[i+j-1];
            x=c[i+j-1]/10;
            c[i+j-1]%=10;
        }
        c[i+lenb]=x;
    }
    //计算 
    lenc=lena+lenb;
    while(c[lenc]==0&&lenc>1)
         lenc--;
    //去掉前导0 
    for( int i=lenc;i>=1;--i)
         cout<<c[i];
    //输出 
}

by Frank_Pu @ 2016-12-20 17:23:42

同问?


by Timothy  @ 2017-01-04 08:27:26

你可以尝试一下FFT


|