euler20

n! means n × (n − 1) × ... × 3 × 2 × 1

Find the sum of the digits in the number 100!
--------------------

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

typedef struct _digit_t {
    char v;
    int base;
    struct _digit_t *next;
} digit_t;

/* invert input */
digit_t *create_digit(char *d)
{
    digit_t *head;
    digit_t *node, *pnode=NULL;
    int i;

    for (i=strlen(d)-1; i >= 0 ; i--) {
        node = malloc(sizeof(digit_t));
        node->v = d[i];
        node->next = NULL;

        if (pnode) {
            pnode->next = node;
            pnode = node;
        } else {
            pnode = node;
            head = node;
        }
    }

    return head;
}

digit_t * mul(digit_t *mul1, digit_t *mul2)
{
    digit_t *result, *pmul1, *pmul2;
    digit_t *node = NULL, *pnode = NULL;
    int carry;
    digit_t *presult = NULL;

    pmul2 = mul2;
    while (pmul2) {
        carry = 0;
        if (presult) {
            presult = presult->next;
            node = presult;
        }
        pmul1 = mul1;
        while (pmul1) {
            if (!node) {
                node = malloc(sizeof(digit_t));
                node->v = '0';
                node->next = NULL;
                if(pnode) {
                    pnode->next = node;
                    pnode = node;
                } else {
                    pnode = node;
                    result = node;
                    presult = result;
                }
            }

            carry += (node->v-'0') + (pmul1->v - '0') * (pmul2->v - '0');
            node->v = carry % 10 + '0';
            carry /= 10;

            node = node->next;
            pmul1 = pmul1->next;
        }
        while (carry) {
            if (!node) {
                node = malloc(sizeof(digit_t));
                node->v = '0';
                node->next = NULL;
                pnode->next = node;
                pnode = node;
            }
            carry += node->v - '0';
            node->v = carry % 10 + '0';
            carry /= 10;
            node = node->next;
        }

        pmul2 = pmul2->next;
    }

    return result;
}

void free_digit(digit_t *p)
{
    digit_t *node=p;

    while (node) {
        digit_t *next = node->next;
        free(node);
        node = next;
    }
}

/* invert output */
void output_digit(digit_t *head)
{
    digit_t *node = head;

    if (!head)
        return;

    output_digit(head->next);
    putchar(node->v);
}

#define N 100
int main(int argc, const char *argv[])
{
    char buf[3];
    int i;
    digit_t *result = create_digit("1");
    digit_t *n;
    int sum = 0;

    for (i=1; i<= N; i++) {
        sprintf(buf, "%d", i);
        n = create_digit(buf);
        result = mul(result, n);
        free_digit(n);
    }

    output_digit(result);

    n = result;
    while (n) {
        sum +=  n->v - '0';
        n = n->next;
    }

    printf("\nsum: %d\n", sum);

    return 0;
}

任意精度的乘法。实现太别扭...