#45867: 解答 c


n0970616056@gmail.com (CIOU-HE-CHEN)

學校 : 不指定學校
編號 : 273811
來源 : [27.51.143.14]
最後登入時間 :
2025-04-21 21:05:24
i212. 三則運算 -- 小學三年級數學習作 | From: [27.51.143.14] | 發表日期 : 2025-04-21 21:05

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

typedef struct { double re, im; } cplx;

cplx add(cplx a, cplx b){ return (cplx){a.re+b.re, a.im+b.im}; }
cplx subc(cplx a, cplx b){ return (cplx){a.re-b.re, a.im-b.im}; }
cplx mulc(cplx a, cplx b){ return (cplx){a.re*b.re - a.im*b.im, a.re*b.im + a.im*b.re}; }

void fft(cplx *a, int n, int invert){
    for(int i=1,j=0;i<n;i++){
        int bit = n>>1;
        for(; j&bit; bit>>=1) j ^= bit;
        j ^= bit;
        if(i<j){ cplx t=a[i]; a[i]=a[j]; a[j]=t; }
    }
    for(int len=2; len<=n; len<<=1){
        double ang = 2*acos(-1)/len * (invert ? -1 : 1);
        cplx wlen = { cos(ang), sin(ang) };
        for(int i=0; i<n; i+=len){
            cplx w = {1,0};
            for(int j=0; j<len/2; j++){
                cplx u = a[i+j];
                cplx v = mulc(a[i+j+len/2], w);
                a[i+j] = add(u, v);
                a[i+j+len/2] = subc(u, v);
                w = mulc(w, wlen);
            }
        }
    }
    if(invert) for(int i=0;i<n;i++) a[i].re /= n;
}

int main(){
    static char sa[1000005], sb[1000005];
    char op;
    if(scanf("%s %c %s", sa, &op, sb)!=3) return 0;
    int na = strlen(sa), nb = strlen(sb);
    if(op=='+'){
        int n = na>nb ? na : nb, carry=0;
        char *s = malloc(n+3);
        s[n+1]=0;
        for(int i=0;i<=n;i++){
            int da = i<na ? sa[na-1-i]-'0' : 0;
            int db = i<nb ? sb[nb-1-i]-'0' : 0;
            int sum = da+db+carry;
            s[n-i] = (sum%10)+'0';
            carry = sum/10;
        }
        if(s[1]=='0'){
            printf("%s\n", s+2);
        } else printf("%s\n", s+1);
        return 0;
    }
    if(op=='-'){
        int n = na>nb ? na : nb, carry=0;
        char *s = malloc(n+1);
        s[n]=0;
        for(int i=0;i<n;i++){
            int da = i<na ? sa[na-1-i]-'0' : 0;
            int db = i<nb ? sb[nb-1-i]-'0' : 0;
            int diff = da - db - carry;
            if(diff<0){ diff+=10; carry=1; } else carry=0;
            s[n-1-i] = diff+'0';
        }
        int i=0;
        while(i<n-1 && s[i]=='0') i++;
        printf("%s\n", s+i);
        return 0;
    }
    // multiplication
    const int BASE = 1000, BASE_DIGITS = 3;
    int la = (na + BASE_DIGITS - 1) / BASE_DIGITS;
    int lb = (nb + BASE_DIGITS - 1) / BASE_DIGITS;
    int n=1;
    while(n < la+lb) n <<=1;
    cplx *fa = calloc(n, sizeof(cplx));
    cplx *fb = calloc(n, sizeof(cplx));
    for(int i=0;i<la;i++){
        int end = na - i*BASE_DIGITS;
        int start = end>BASE_DIGITS ? end-BASE_DIGITS : 0;
        int x = 0;
        for(int j=start;j<end;j++) x = x*10 + (sa[j]-'0');
        fa[i].re = x;
    }
    for(int i=0;i<lb;i++){
        int end = nb - i*BASE_DIGITS;
        int start = end>BASE_DIGITS ? end-BASE_DIGITS : 0;
        int x = 0;
        for(int j=start;j<end;j++) x = x*10 + (sb[j]-'0');
        fb[i].re = x;
    }
    fft(fa, n, 0);
    fft(fb, n, 0);
    for(int i=0;i<n;i++) fa[i] = mulc(fa[i], fb[i]);
    fft(fa, n, 1);
    long long *res = calloc(n, sizeof(long long));
    for(int i=0;i<n;i++) res[i] = (long long)(fa[i].re + 0.5);
    long long carry = 0;
    for(int i=0;i<n;i++){
        long long cur = res[i] + carry;
        res[i] = cur % BASE;
        carry = cur / BASE;
    }
    int sz = n;
    while(sz>1 && res[sz-1]==0) sz--;
    printf("%lld", res[sz-1]);
    for(int i=sz-2;i>=0;i--) printf("%03lld", res[i]);
    printf("\n");
    return 0;
}

 
ZeroJudge Forum