高精度模板

2018-06-17 23:49:04来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

#include <cstring>
#include <cstdio>
#include <cstdlib>
#define MAX 200
using namespace std;

typedef struct
{
    int len;
    int s[MAX+1];
} hp;

void input(hp *a, int x) //读入数字
{
    int i;

    a->len = 0;

    while (x > 0)
    {
        a->s[1 + a->len++] = x % 10;
        x /= 10;
    }

    for (i = a->len + 1; i <= MAX; i++)
        a->s[i] = 0;
}

void input1(hp *a, char *str) //读入字符串
{
    int i, len;

    a->len = 0;

    if (str == NULL)
        return;

    len = strlen(str);

    while (len > 0)
    {
        a->s[1 + a->len++] = *(str + len - 1) - '0';
        len--;
    }

    for (i = a->len + 1; i <= MAX; i++)
        a->s[i] = 0;
}

void print(hp *y) //打印数字
{
    int i;
    for (i = y->len; i >= 1; i--)
        printf("%d", y->s[i]);
    printf("\n");
}

void add(hp *a, hp *b, hp *c) //高精度加法c = a + b
{
    int i, len;

    for (i = 1; i <= MAX; i++) c->s[i] = 0;

    if (a->len > b->len) len = a->len;
    else len = b->len;

    for (i = 1; i <= len; i++)
    {
        c->s[i] += a->s[i] + b->s[i];
        if (c->s[i] >= 10)
        {
            c->s[i] -= 10;
            c->s[i+1]++;
        }
    }

    if (c->s[len+1] > 0) len++;
    c->len = len;
}

void subtract(hp *a, hp *b, hp *c) //高精度减法c = a - b
{
    int i, len;

    for (i = 1; i <= MAX; i++) c->s[i] = 0;

    if (a->len > b->len) len = a->len;
    else len = b->len;

    for (i = 1; i <= len; i++)
    {
        c->s[i] += a->s[i] - b->s[i];
        if (c->s[i] < 0)
        {
            c->s[i] += 10;
            c->s[i+1]--;
        }
    }

    while (len > 1 && c->s[len] == 0) len--;
    c->len = len;
}

int compare(hp *a, hp *b) //高精度比较
{
    int len;

    if (a->len > b->len) len = a->len;
    else len = b->len;

    while (len > 0 && a->s[len] == b->s[len]) len--;

    if (len == 0) return 0;
    else return a->s[len] - b->s[len];
}

void multiply(hp *a, int b, hp *c) //高精度 * 单精度
{
    int i, len;

    for (i = 1; i <= MAX; i++) c->s[i] = 0;
    len = a->len;

    for (i = 1; i <= len; i++)
    {
        c->s[i] += a->s[i] * b;
        c->s[i+1] += c->s[i] / 10;
        c->s[i] %= 10;
    }

    len++;
    while (c->s[len] >= 10)
    {
        c->s[len+1] += c->s[len] / 10;
        c->s[len] %= 10;
        len++;
    }

    while (len > 1 && c->s[len] == 0) len--;
    c->len = len;
}

void multiplyh(hp *a, hp *b, hp *c) //高精度 * 高精度
{
    int i, j, len;

    for (i = 1; i <= MAX; i++) c->s[i] = 0;

    for (i = 1; i <= a->len; i++)
    {
        for (j = 1; j <= b->len; j++)
        {
            c->s[i+j-1] += a->s[i] * b->s[j];
            c->s[i+j] += c->s[i+j-1] / 10;
            c->s[i+j-1] %= 10;
        }
    }

    len = a->len + b->len + 1;
    while (len > 1 && c->s[len] == 0) len--;
    c->len = len;
}

void power(hp *a, int b, hp *c) //高精度乘方c = a ^ b
{
    hp e;

    if (b == 0)
    {
        c->len = 1;
        c->s[1] = 1;
    }
    else if (b == 1)
    {
        memcpy(c, a, sizeof(hp));
    }
    else
    {
        power(a, b / 2, &e);
        multiplyh(&e, &e, c);

        if (b % 2 == 1)
        {
            memcpy(&e, c, sizeof(hp));
            multiplyh(&e, a, c);
        }
    }
}

void divide(hp *a, int b, hp *c, int *d) //高精度 / 单精度 {d为余数}
{
    int i, len;

    for (i = 1; i <= MAX; i++) c->s[i] = 0;
    len = a->len;
    *d = 0;

    for (i = len; i >= 1; i--)
    {
        *d = *d * 10 + a->s[i];
        c->s[i] = *d / b;
        *d %= b;
    }

    while (len > 1 && c->s[len] == 0) len--;
    c->len = len;
}

void multiply10(hp *a) //高精度 * 10
{
    int i;
    for (i = a->len; i >= 1; i--)
        a->s[i+1] = a->s[i];

    a->s[1] = 0;
    a->len++;
    while (a->len > 1 && a->s[a->len] == 0) a->len--;
}

void divideh(hp *a, hp *b, hp *c, hp *d) //高精度 / 高精度{d为余数}
{
    hp e;
    int i, len;

    for (i = 1; i <= MAX; i++)
    {
        c->s[i] = 0;
        d->s[i] = 0;
    }

    len = a->len;
    d->len = 1;

    for (i = len; i >= 1; i--)
    {
        multiply10(d);
        d->s[1] = a->s[i];

        while (compare(d, b) >= 0)
        {
            subtract(d, b, &e);
            *d = e;
            c->s[i]++;
        }
    }

    while (len > 1 && c->s[len] == 0) len--;
    c->len = len;
}
int main()
{
    return 0;
}

 非本人原创,转载地址忘写了。。。

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:【NOIP训练】【规律+数论】欧拉函数的应用

下一篇:HDU 1141---Brackets Sequence(区间DP)