e024: 少年πの超大數運算(1)

2019-09-09

內容

大家對大數運算肯定不陌生

我就不解釋了

大家請看題目

輸入

給你兩個數 n,m (0<n,m<=100000),求 n^m

一行兩個以空白隔開的正整數,以 0 0 結尾

1 1
1 2
1 10000
0 0

輸出

輸出 n^m

1
1
1

解題思路

先建好一個有乘法的大數結構，再用大數乘法配合快速冪算出答案後輸出即可。

以下是優化部分

大數用千萬進制做完乘法後再進位速度遠高於十億進制一邊乘一邊進位。
除法和取餘運算很久，改成用除法得到商後再將原數減去除法得到的商乘上一千萬，也就是將

a = n / 10;
b = n % 10;

改成

a = n / 10;
b = n - (a * 10);

不過 10 要改成 1000 萬
乘法用左移運算加速
用指標減少記憶體操作量
輸入輸出優化

第一項特別重要，它讓我從 TLE(10s) 變成 AC(2.3s)，其餘的不做應該也能過但時間就不會太好看。

完整程式碼

AC (1.9s, 2.2MB)

#pragma GCC optimize(3)
#include <stdio.h>
#include <memory.h>
#define BUFSIZ 1048576
#define MOD 10000000
#define MUTMOD(x) ((x<<24)-(x<<22)-(x<<21)-(x<<19)+(x<<16)-(x<<14)-(x<<13)-(x<<11)-(x<<8)-(x<<7))

typedef struct BigNum
{
    unsigned long long Num[72000];
    int Last;
}BigNum;

BigNum list[3], * n = &list[0], * ans = &list[1], * tmp = &list[2];
char output[500050];

inline char readChar()
{
    static char buffer[BUFSIZ], * now = buffer + BUFSIZ, * end = buffer + BUFSIZ;
    if (now == end)
    {
        if (end < buffer + BUFSIZ)
            return EOF;
        end = (buffer + fread(buffer, 1, BUFSIZ, stdin));
        now = buffer;
    }
    return *now++;
}

inline char readUInt(unsigned int* dst)
{
    register char ch;
    while ((ch = readChar()) < '0')
        if (ch == EOF) return 0;
    *dst = ch ^ '0';
    while ((ch = readChar()) >= '0')
        * dst = (*dst << 3) + (*dst << 1) + (ch ^ '0');
    return 1;
}

inline BigNum* BigMult(BigNum* dst, BigNum* times)
{
    memset(tmp, 0, sizeof(BigNum));
    tmp->Last = dst->Last + times->Last;
    register unsigned long long div;
    for (int i = 0; i <= dst->Last; i++)
    {
        if (dst->Num[i])
        {
            for (int j = 0; j <= times->Last; j++)
            {
                if (times->Num[j])
                    tmp->Num[i + j] += dst->Num[i] * times->Num[j];
            }
        }
    }
    for (int i = 0; i <= tmp->Last; i++)
    {
        if (tmp->Num[i] >= MOD)
        {
            div = tmp->Num[i] / MOD;
            tmp->Num[i] = tmp->Num[i] - MUTMOD(div);
            tmp->Num[i + 1] += div;
            if (tmp->Last < i + 1)
                tmp->Last = i + 1;
        }
    }
    BigNum* res = tmp;
    tmp = dst;
    return res;
}

void pow(BigNum* dst, BigNum* src, int m)
{
    dst->Num[0] = 1, dst->Last = 0;
    for (;; m >>= 1)
    {
        if (m & 1)
        {
            dst = BigMult(dst, src);
            if (m == 1)
                break;
        }
        src = BigMult(src, src);
    }
    ans = dst;
    n = src;
}

void putUBigNum(char buffer[], BigNum* src)
{
    register char* st = buffer;
    register unsigned long long div1, div2;
    for (int i = src->Last; ~i; i--, st += 7)
    {
        st[6] = (src->Num[i] - ((div1 = src->Num[i] / 10) << 3) - (div1 << 1)) | '0';
        st[5] = (div1 - ((div2 = div1 / 10) << 3) - (div2 << 1)) | '0';
        st[4] = (div2 - ((div1 = div2 / 10) << 3) - (div1 << 1)) | '0';
        st[3] = (div1 - ((div2 = div1 / 10) << 3) - (div2 << 1)) | '0';
        st[2] = (div2 - ((div1 = div2 / 10) << 3) - (div1 << 1)) | '0';
        st[1] = (div1 - ((div2 = div1 / 10) << 3) - (div2 << 1)) | '0';
        st[0] = (div2 - ((div1 = div2 / 10) << 3) - (div1 << 1)) | '0';
    }
    *st = '\0', st = buffer;
    while (*st == '0')
        st++;
    puts(st);
}

int main()
{
    int m;
    while ((readUInt(&n->Num[0]), readUInt(&m)) && n->Num[0] + m)
    {
        n->Last = 0;
        pow(ans, n, m);
        putUBigNum(output, ans);
    }
    return 0;
}