51 Nod 1028 大数乘法 V2 NTT 学习

题意：求两个大数的乘积
解题方法：之前已经用FFT做过了，今天学习一下NTT，记录一下模板。
先所以下NTT，具体的讲解可以看见这里 为了避免FFT在复数和浮点运算中出现精度问题，所以在某些情况下使用NTT。记录一下NTT的模板，其实和FFT很多一样。对了这个具体原理可以看这个博客：见这里

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1<<18;
const int G = 3,P = (479<<21) + 1; //G为原根，P为大素数,可以处理2^21次范围

LL quick(LL x,LL n) {
    LL ret = 1;
    for(; n; n >>= 1) {
        if(n & 1) ret = ret * x % P;
        x = x * x % P;
    }
    return ret;
}

LL A[N],B[N];
void rader(LL* y,int len) {
    for(int i = 1,j = len / 2; i < len - 1; i++) {
        if(i < j) swap(y[i],y[j]);
        int k = len / 2;
        while(j >= k) {j -= k; k /= 2;}
        if(j < k) j += k;
    }
}
void ntt(LL* y,int len,int op) {
    rader(y,len);
    for(int h = 2; h <= len; h <<= 1) {
        LL wn = quick(G,(P - 1) / h);
        if(op == -1) wn = quick(wn,P - 2);
        for(int j = 0; j < len; j += h) {
            LL w = 1;
            for(int k = j; k < j + h / 2; k++) {
                LL u = y[k];
                LL t = w * y[k + h / 2] % P;
                y[k] = (u + t) % P;
                y[k + h / 2] = (u - t + P) % P;
                w = w * wn % P;
            }
        }
    }
    if(op == -1) {
        LL inv = quick(len,P - 2);
        for(int i = 0; i < len; i++) y[i] = y[i] * inv % P;
    }
}
char s1[100010],s2[100010];
LL ans[N];

int main()
{
    while(scanf("%s%s",s1,s2) != EOF)
    {
        int len1 = strlen(s1);
        int len2 = strlen(s2);
        memset(A,0,sizeof(A));
        memset(B,sizeof(B));
        for(int i = len1 - 1; i >= 0; i--) A[i] = s1[len1-i-1] - '0';
        for(int i = len2 - 1; i >= 0; i--) B[i] = s2[len2-i-1] - '0';
        int len = 1;
        while(len < len1 * 2 || len < len2 * 2) len <<= 1;
        ntt(A,len,1);
        ntt(B,1);
        for(int i = 0; i < len; i++) A[i] = A[i] * B[i] % P;
        ntt(A,-1);
        memset(ans,sizeof(ans));
        for(int i = 0; i < len; i++){
            ans[i] += A[i];
            if(ans[i] >= 10){
                ans[i+1] += ans[i]/10;
                ans[i]%=10;
            }
        }
        int pos = 0;
        for(int i = len-1; i >= 0; i--){
            if(ans[i]){
                pos = i;
                break;
            }
        }
        for(int i = pos; i >= 0; i--){
            printf("%lld",ans[i]);
        }
        printf("n");
    }
    return 0;
}

（编辑：淮安站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!