首页 > 代码库 > hdu 1402 A * B Problem Plus （FFT + 大数相乘）

hdu 1402 A * B Problem Plus （FFT + 大数相乘）

2024-11-10 16:06:39   203人阅读

A * B Problem Plus

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 13456    Accepted Submission(s): 2401


Problem Description
Calculate A * B.
 

Input
Each line will contain two integers A and B. Process to end of file.

Note: the length of each integer will not exceed 50000.
 

Output
For each case, output A * B in one line.
 

Sample Input
1
2
1000
2
 

Sample Output
2
2000
 


干完这题，对FFT有了点感觉。


#include <iostream>
#include <string>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
const double pi=acos(-1.0);
const int maxn=50010;

struct Complex
{
    double a,b;
    Complex(){}
    Complex(double _a,double _b):a(_a),b(_b){}
    Complex operator + (const Complex &c)
    {
        return Complex(a+c.a,b+c.b);
    }
    Complex operator - (const Complex &c)
    {
        return Complex(a-c.a,b-c.b);
    }
    Complex operator * (const Complex &c)
    {
        return Complex(a*c.a-b*c.b,a*c.b+b*c.a);
    }
}num1[maxn*4],num2[maxn*4];

string str1,str2;
int cnt,ans[maxn*4];

void ready()
{
    cnt=1;
    int len1=str1.size(),len2=str2.size();
    while(cnt<2*len1 || cnt<2*len2)  cnt<<=1;

    for(int i=len1-1,j=0;i>=0;i--,j++)   num1[j]=Complex(str1[i]-'0',0);
    for(int i=len1;i<=cnt;i++)   num1[i]=Complex(0,0);

    for(int i=len2-1,j=0;i>=0;i--,j++)   num2[j]=Complex(str2[i]-'0',0);
    for(int i=len2;i<=cnt;i++)   num2[i]=Complex(0,0);
}

void change(Complex s[],int len)
{
    for(int i=1,j=len/2;i<len-1;i++)
    {
        if(i<j)  swap(s[i],s[j]);
        int k=len/2;
        while(j>=k)
        {
            j-=k;
            k/=2;
        }
        if(j<k) j+=k;
    }
}

void FFT(Complex s[],int len,int on)
{
    change(s,len);
    for(int i=2;i<=len;i<<=1)
    {
        Complex wn=Complex(cos(-on*2*pi/i),sin(-on*2*pi/i));
        for(int j=0;j<len;j+=i)
        {
            Complex w(1,0);
            for(int k=j;k<j+i/2;k++)
            {
                 Complex u=s[k];
                 Complex t=w*s[k+i/2];
                 s[k]=u+t;
                 s[k+i/2]=u-t;
                 w=w*wn;
            }
        }
    }
    if(on==-1)
    {
        for(int i=0;i<len;i++)
           s[i].a/=len;
    }
}

void deal()
{
    FFT(num1,cnt,1);
    FFT(num2,cnt,1);
    for(int i=0;i<cnt;i++)   num1[i]=num1[i]*num2[i];
    FFT(num1,cnt,-1);
}

void solve()
{
    for(int i=0;i<cnt;i++)  ans[i]=(int)(num1[i].a+0.5);

    for(int i=0;i<cnt;i++)
    {
        ans[i+1]=ans[i+1]+ans[i]/10;
        ans[i]=ans[i]%10;
    }
    cnt=str1.size()+str2.size()-1;
    while(ans[cnt]==0 && cnt>0) cnt--;
    for(int i=cnt;i>=0;i--)  putchar(ans[i]+'0');
    putchar('\n');
}

int main()
{
    while(cin>>str1>>str2)
    {
          ready();
          deal();
          solve();
    }
    return 0;
}



hdu 1402 A * B Problem Plus （FFT + 大数相乘）


联系
我们