首页 > 代码库 > 高精度模板

高精度模板

#include <cstring>#include <cstdio>#include <cstdlib>#define MAX 200using 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;}

 

高精度模板