HDU 1402 A * B fft 板子题

　　题目链接： http://acm.hdu.edu.cn/showproblem.php?pid=1402

　　题目描述：计算A * B，其中A， B是长度小于等于50000的整数

　　解题思路：放在以前我可能会拿两个高精度的乘法来计算，但现在我接触到了fft：求值 -> 相乘 -> 插值。下面是一篇很好的 fft 的讲解：

　　　　　　　 http://www.gatevin.moe/acm/fft%E7%AE%97%E6%B3%95%E5%AD%A6%E4%B9%A0%E7%AC%94%E8%AE%B0/

　　　　　　　首先我们把A， B分解成系数表达式，也就是十进制表示的所有系数前面的整数，如12345就是(1,2,3,4,5)，然后fft, 板子题。　　

　　题目代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;

const double PI = acos(-1.0);
struct Complex {
    double x, y;
    Complex(double _x = 0.0, double _y = 0.0) {
        x = _x;
        y = _y;
    }
    Complex operator -(const Complex & b )const {
        return Complex(x-b.x, y-b.y);
    }
    Complex operator +(const Complex & b)const {
        return Complex(x+b.x, y+b.y);
    }
    Complex operator *(const Complex & b)const {
        return Complex(x*b.x-y*b.y, x*b.y+y*b.x);
    }
};
void change(Complex y[], int len) {
    int i, j, k;
    for(i = 1, j = len / 2; i < len - 1; i++ ) {
        if( i < j ) swap( y[i], y[j] );
        k = len / 2;
        while( j >= k ) {
            j -= k;
            k /= 2;
        }
        if( j < k ) j += k;
    }
}
void fft(Complex y[], int len, int on) {
    change( y, len );
    for( int h = 2; h <= len; h <<= 1 ) {
        Complex wn( cos(-on*2*PI/h), sin(-on*2*PI/h) );
        for( int j = 0; j < len; j += h) {
            Complex w(1, 0);
            for( int k = j; k < j + h / 2; k++ ) {
                Complex u = y[k];
                Complex t = w * y[k+h/2];
                y[k] = u + t;
                y[k+h/2] = u - t;
                w = w * wn;
            }
        }
    }
    if( on == -1 ) {
        for( int i = 0; i < len; i++ ) {
            y[i].x /= len;
        }
    }
}
const int MAXN = 200010;
Complex x1[MAXN], x2[MAXN];
char str1[MAXN/2], str2[MAXN/2];
int sum[MAXN];

int main() {
    while( scanf( "%s%s", str1, str2 ) == 2 ) {
        int len1 = (int)strlen(str1);
        int len2 = (int)strlen(str2);
        int len = 1;
        while( len < len1 * 2 || len < len2 * 2 ) len <<= 1;
        for( int i = 0; i < len1; i++ ) {
            x1[i] = Complex(str1[len1-1-i]-'0', 0);
        }
        for( int i = len1; i < len; i++ ) {
            x1[i] = Complex(0,0);
        }
        for( int i = 0; i < len2; i++ ) {
            x2[i] = Complex(str2[len2-1-i]-'0', 0);
        }
        for( int i = len2; i < len; i++ ) {
            x2[i] = Complex(0,0);
        }
        fft( x1, len, 1 );
        fft( x2, len, 1 );
        for( int i = 0; i < len; i++ ) {
            x1[i] = x1[i] * x2[i];
        }
        fft( x1, len, -1 );
        for( int i = 0; i < len; i++ ) {
            sum[i] = (int)(x1[i].x + 0.5);
        }
        for( int i = 0; i < len; i++ ) {
            sum[i+1] += sum[i] / 10;
            sum[i] %= 10;
        }
        len = len1 + len2 -1;
        while( sum[len] <= 0 && len > 0 ) len--;
        for( int i = len; i >= 0; i-- ) {
            printf( "%c", sum[i] + '0' );
        }
        printf( "\n" );
    }
    return 0;
}

View Code

　　思考：多做数学题， fft, 高斯消元，欧几里得定理等等。