euler 48: 大整数乘法

euler project 48:

The series, 1¹ + 2² + 3³ + ... + 10¹⁰ = 10405071317.

Find the last ten digits of the series, 1¹ + 2² + 3³ + ... + 1000¹⁰⁰⁰.

我是用python解的,python 的数没有大小的限制,这样就很方便,brute force.

在问题的讨论帖中,有人(grimbal)贴了他用C解决的算法。我觉得很优美，记录如下:

#define mod 10000
void ex48(){
    int n, k;
    unsigned int p2, p1, p0;
    unsigned int s2, s1, s0;
    unsigned int t2, t1, t0;

    // s = 0
    s2 = s1 = s0 = 0;
    for( n=1 ; n<=1000 ; n++ ){
        // p = 1
        p2 = p1 = 0; p0 = 1;
        for( k=1 ; k<=n ; k<<=1 );
        while( k>>=1 ){
            // p *= p
            t0 = p0*p0;
            t1 = 2*p0*p1 + t0/mod;
            t2 = 2*p0*p2 + p1*p1 + t1/mod;
            p0 = t0%mod;
            p1 = t1%mod;
            p2 = t2%mod;
            if( n&k ){
                // p *= n
                t0 = p0*n;
                t1 = p1*n + t0/mod;
                t2 = p2*n + t1/mod;
                p0 = t0%mod;
                p1 = t1%mod;
                p2 = t2%mod;
            }
       }
       // s += p
       t0 = p0+s0;
       t1 = p1+s1 + t0/mod;
       t2 = p2+s2 + t1/mod;
       s0 = t0%mod;
       s1 = t1%mod;
       s2 = t2%mod;
    }

    printf("ex48: %02d%04d%04d\n", s2%100, s1, s0);
}