poj 2389：

Description

Input

Output

Sample Input

22222222221111
2222222222

Sample Output

12345679011110987654321

code：

#include <iostream>
#include <stdio.h>
#include<string.h>
#include<malloc.h>
using namespace std;
int s[100];
void multiply(const char *a,const char *b)
{
    int i,j,ca,cb;
    //int *s;
    ca=strlen(a);
    cb=strlen(b);
    //s=(int *)malloc(sizeof(int)*(ca+cb));
    for (i=0; i<ca+cb; i++)
        s[i]=0;

    for (i=0; i<ca; i++)
        for (j=0; j<cb; j++)
            s[i+j+1]+=(a[i]-'0')*(b[j]-'0');

    for (i=ca+cb-1; i>=0; i--) //进位
        if (s[i]>=10)
        {
            s[i-1]+=s[i]/10;
            s[i]%=10;
        }
    i=0;
    for(i=0; i<ca+cb; i++)
        if(s[i]!=0)
            break;// 跳过头部0元素
    if(i==ca+cb)
    {
        printf("0n");
        return ;
    }
    for(; i<ca+cb; i++)
        cout<<s[i];
    cout<<endl;
}
int main()
{
    char a[51],b[51];
    while(scanf("%s%s",a,b)!=EOF)
    {
        multiply(a,b);
    }
    return 0;
}

hdu 1402：点击打开链接

A * B Problem Plus

  
  

   
   1
2
1000
2
  
  

  
  

   
   2
2000
  
  

FFT模板：转载：题解链接

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
#define L(x) (1 << (x))

const double PI = acos(-1.0);
const int Maxn = 133015;
double ax[Maxn],ay[Maxn],bx[Maxn],by[Maxn];
char sa[Maxn/2],sb[Maxn/2];
int sum[Maxn];
int x1[Maxn],x2[Maxn];

int revv(int x,int bits)
{
    int ret = 0;
    for (int i = 0; i < bits; i++)
    {
        ret <<= 1;
        ret |= x & 1;
        x >>= 1;
    }
    return ret;
}
void fft(double * a,double * b,int n,bool rev)
{
    int bits = 0;
    while (1 << bits < n) ++bits;
    for (int i = 0; i < n; i++)
    {
        int j = revv(i,bits);
        if (i < j)
            swap(a[i],a[j]),swap(b[i],b[j]);
    }
    for (int len = 2; len <= n; len <<= 1)
    {
        int half = len >> 1;
        double wmx = cos(2 * PI / len),wmy = sin(2 * PI / len);
        if (rev) wmy = -wmy;
        for (int i = 0; i < n; i += len)
        {
            double wx = 1,wy = 0;
            for (int j = 0; j < half; j++)
            {
                double cx = a[i + j],cy = b[i + j];
                double dx = a[i + j + half],dy = b[i + j + half];
                double ex = dx * wx - dy * wy,ey = dx * wy + dy * wx;
                a[i + j] = cx + ex,b[i + j] = cy + ey;
                a[i + j + half] = cx - ex,b[i + j + half] = cy - ey;
                double wnx = wx * wmx - wy * wmy,wny = wx * wmy + wy * wmx;
                wx = wnx,wy = wny;
            }
        }
    }
    if (rev)
    {
        for (int i = 0; i < n; i++)
            a[i] /= n,b[i] /= n;
    }
}
int solve(int a[],int na,int b[],int nb,int ans[])
{
    int len = max(na,nb),ln;
    for(ln=0; L(ln)<len; ++ln);
    len=L(++ln);
    for (int i = 0; i < len ; ++i)
    {
        if (i >= na) ax[i] = 0,ay[i] =0;
        else ax[i] = a[i],ay[i] = 0;
    }
    fft(ax,ay,len,0);
    for (int i = 0; i < len; ++i)
    {
        if (i >= nb) bx[i] = 0,by[i] = 0;
        else bx[i] = b[i],by[i] = 0;
    }
    fft(bx,by,0);
    for (int i = 0; i < len; ++i)
    {
        double cx = ax[i] * bx[i] - ay[i] * by[i];
        double cy = ax[i] * by[i] + ay[i] * bx[i];
        ax[i] = cx,ay[i] = cy;
    }
    fft(ax,1);
    for (int i = 0; i < len; ++i)
        ans[i] = (int)(ax[i] + 0.5);
    return len;
}

int main()
{
    int l1,l2,l;
    int i;
    while(gets(sa))
    {
        gets(sb);
        memset(sum,sizeof(sum));
        l1 = strlen(sa);
        l2 = strlen(sb);

        for(i = 0; i < l1; i++)
            x1[i] = sa[l1 - i - 1]-'0';

        for(i = 0; i < l2; i++)
            x2[i] = sb[l2-i-1]-'0';

        l = solve(x1,l1,x2,sum);

        for(i = 0; i<l || sum[i] >= 10; i++) // 进位
        {
            sum[i + 1] += sum[i] / 10;
            sum[i] %= 10;
        }

        l = i;
        while(sum[l] <= 0 && l>0)    l--; // 检索最高位
        for(i = l; i >= 0; i--)    putchar(sum[i] + '0'); // 倒序输出
        putchar('n');
    }
    return 0;
}