【HDU】1402 A * B Problem Plus 【FFT】

傳送門：【HDU】1402 A * B Problem Plus

題目分析：

這就是大數乘法題，問兩個大數相乘的結果，由于 O(n2) 的算法複雜度太大，是以我們用FFT來優化他。關于FFT網上資料很多，我就不多說啦。

這是我做的第一道FFT，FFT是看算法導論學來的，感覺算導講的很不錯，簡單易懂~

my code：

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <algorithm>
using namespace std ;

typedef long long LL ;

#define clr( a , x ) memset ( a , x , sizeof a )
#define cpy( a , x ) memcpy ( a , x , sizeof a )

const int MAXN =  ;
const double pi = acos ( - ) ;

struct Complex {
    double r , i ;
    Complex () {}
    Complex ( double r , double i ) : r ( r ) , i ( i ) {}
    Complex operator + ( const Complex& t ) const {
        return Complex ( r + t.r , i + t.i ) ;
    }
    Complex operator - ( const Complex& t ) const {
        return Complex ( r - t.r , i - t.i ) ;
    }
    Complex operator * ( const Complex& t ) const {
        return Complex ( r * t.r - i * t.i , r * t.i + i * t.r ) ;
    }
} ;

void FFT ( Complex y[] , int n , int rev ) {
    for ( int i =  , j , k , t ; i < n ; ++ i ) {
        for ( j =  , k = n >>  , t = i ; k ; k >>=  , t >>=  ) j = j <<  | t &  ;
        if ( i < j ) swap ( y[i] , y[j] ) ;
    }
    for ( int s =  , ds =  ; s <= n ; ds = s , s <<=  ) {
        Complex wn = Complex ( cos ( rev *  * pi / s ) , sin ( rev *  * pi / s ) ) , w = Complex (  ,  ) , t ;
        for ( int k =  ; k < ds ; ++ k , w = w * wn ) {
            for ( int i = k ; i < n ; i += s ) {
                y[i + ds] = y[i] - ( t = w * y[i + ds] ) ;
                y[i] = y[i] + t ;
            }
        }
    }
    if ( rev == - ) for ( int i =  ; i < n ; ++ i ) y[i].r /= n ;
}

char s1[MAXN] , s2[MAXN] ;
Complex x1[MAXN] , x2[MAXN] ;
int num[MAXN] ;

void solve () {
    int n1 = strlen ( s1 ) ;
    int n2 = strlen ( s2 ) ;
    int n =  ;
    while ( n < n1 + n2 ) n <<=  ;
    for ( int i =  ; i < n1 ; ++ i ) x1[i] = Complex ( s1[n1 - i - ] - '0' ,  ) ;
    for ( int i = n1 ; i < n ; ++ i ) x1[i] = Complex (  ,  ) ;
    for ( int i =  ; i < n2 ; ++ i ) x2[i] = Complex ( s2[n2 - i - ] - '0' ,  ) ;
    for ( int i = n2 ; i < n ; ++ i ) x2[i] = Complex (  ,  ) ;
    FFT ( x1 , n ,  ) ;
    FFT ( x2 , n ,  ) ;
    for ( int i =  ; i < n ; ++ i ) x1[i] = x1[i] * x2[i] ;
    FFT ( x1 , n , - ) ;
    int t =  ;
    for ( int i =  ; i < n ; ++ i , t /=  ) {
        t += ( int ) ( x1[i].r +  ) ;
        num[i] = t %  ;
    }
    for ( ; t ; t /=  ) num[n ++] = t %  ;
    while ( n >  && !num[n - ] ) -- n ;
    for ( int i = n -  ; i >=  ; -- i ) printf ( "%d" , num[i] ) ;
    printf ( "\n" ) ;
}

int main () {
    while ( ~scanf ( "%s%s" , s1 , s2 ) ) solve () ;
    return  ;
}