文档章节

hdu 1002 大数模板

 阿豪boy
发布于 2017/09/08 23:40
字数 1834
阅读 13
收藏 0

完整版 

#include <iostream>
#include <cstring>
#include <iomanip>
#include <algorithm>

using namespace std;

#define MAXN 9999
#define MAXSIZE 10
#define DLEN 4

class BigNum {
private:
    int a[500];//可以控制大数的位数
    int len;//大数长度
public:
    BigNum(){
        len = 1;
        memset(a, 0, sizeof(a));
    }//构造函数
    BigNum(const int);//将一个int类型的变量转化为大数
    BigNum(const char*);//将一个字符串类型的变量转化为大数
    BigNum(const BigNum &);//拷贝构造函数
    BigNum &operator = (const BigNum &);//重载赋值运算符,大数之间进行赋值运算

    friend istream& operator >> (istream&, BigNum&);//重载输入运算符
    friend ostream& operator << (ostream&, BigNum&);//重载输出运算符

    BigNum operator + (const BigNum &) const;//重载加法运算符,两个大数之间的相加运算
    BigNum operator - (const BigNum &) const;//重载减法运算符,两个大数之间的相减运算
    BigNum operator * (const BigNum &) const;//重载乘法运算符,两个大数之间的相乘运算
    BigNum operator / (const int   &) const;//重载除法运算符,大数对一个整数进行相除运算

    BigNum operator ^ (const int  &) const;//大数的n次方运算
    int operator % (const int  &) const;//大数对一个int类型的变量进行取模运算
    bool operator > (const BigNum & T) const;//大数和另一个大数的大小比较
    bool operator > (const int & t) const;//大数和一个int类型的变量的大小比较

    void print();//输出大数
};
BigNum::BigNum(const int b){//将一个int类型的变量转化为大数
    int c, d = b;
    len = 0;
    memset(a, 0, sizeof(a));
    while (d > MAXN){
        c = d - (d / (MAXN + 1)) * (MAXN + 1);
        d = d / (MAXN + 1);
        a[len++] = c;
    }
    a[len++] = d;
}
BigNum::BigNum(const char*s){//将一个字符串类型的变量转化为大数
    int t, k, index, l, i;
    memset(a, 0, sizeof(a));
    l = strlen(s);
    len = l / DLEN;
    if (l % DLEN)
        len++;
    index = 0;
    for (i = l - 1; i >= 0; i -= DLEN){
        t = 0;
        k = i - DLEN + 1;
        if (k < 0)
            k = 0;
        for (int j = k; j <= i; j++)
            t = t * 10 + s[j] - '0';
        a[index++] = t;
    }
}
BigNum::BigNum(const BigNum & T) : len(T.len){//拷贝构造函数
    int i;
    memset(a, 0, sizeof(a));
    for (i = 0; i < len; i++)
        a[i] = T.a[i];
}
BigNum & BigNum::operator = (const BigNum & n){//重载赋值运算符,大数之间进行赋值运算
    int i;
    len = n.len;
    memset(a, 0, sizeof(a));
    for (i = 0; i < len; i++)
        a[i] = n.a[i];
    return *this;
}
istream& operator >> (istream & in, BigNum & b){//重载输入运算符
    char ch[MAXSIZE * 4];
    int i = -1;
    in >> ch;
    int l = strlen(ch);
    int count = 0, sum = 0;
    for (i = l - 1; i >= 0; ){
        sum = 0;
        int t = 1;
        for (int j = 0; j < 4 && i >= 0; j++, i--, t *= 10){
            sum += (ch[i] - '0') * t;
        }
        b.a[count] = sum;
        count++;
    }
    b.len = count++;
    return in;

}
ostream& operator << (ostream& out, BigNum& b){//重载输出运算符
    int i;
    cout << b.a[b.len - 1];
    for (i = b.len - 2; i >= 0; i--){
        cout.width(DLEN);
        cou
        t.fill('0');
        cout << b.a[i];
    }
    return out;
}

BigNum BigNum::operator + (const BigNum & T) const//两个大数之间的相加运算
{
    BigNum t(*this);
    int i, big;//位数
    big = T.len > len ? T.len : len;
    for (i = 0; i < big; i++){
        t.a[i] += T.a[i];
        if (t.a[i] > MAXN){
            t.a[i + 1]++;
            t.a[i] -= MAXN + 1;
        }
    }
    if (t.a[big] != 0)
        t.len = big + 1;
    else
        t.len = big;
    return t;
}
BigNum BigNum::operator - (const BigNum & T) const//两个大数之间的相减运算
{
    int i, j, big;
    bool flag;
    BigNum t1, t2;
    if (*this > T){
        t1 = *this;
        t2 = T;
        flag = 0;
    } else {
        t1 = T;
        t2 = *this;
        flag = 1;
    }
    big = t1.len;
    for (i = 0; i < big; i++){
        if (t1.a[i] < t2.a[i]){
            j = i + 1;
            while (t1.a[j] == 0)
                j++;
            t1.a[j--]--;
            while (j > i)
                t1.a[j--] += MAXN;
            t1.a[i] += MAXN + 1 - t2.a[i];
        } else
            t1.a[i] -= t2.a[i];
    }
    t1.len = big;
    while (t1.a[len - 1] == 0 && t1.len > 1){
        t1.len--;
        big--;
    }
    if (flag)
        t1.a[big - 1] = 0 - t1.a[big - 1];
    return t1;
}

BigNum BigNum::operator * (const BigNum & T) const//两个大数之间的相乘运算
{
    BigNum ret;
    int i, j, up;
    int temp, temp1;
    for (i = 0; i < len; i++){
        up = 0;
        for (j = 0; j < T.len; j++){
            temp = a[i] * T.a[j] + ret.a[i + j] + up;
            if (temp > MAXN){
                temp1 = temp - temp / (MAXN + 1) * (MAXN + 1);
                up = temp / (MAXN + 1);
                ret.a[i + j] = temp1;
            } else {
                up = 0;
                ret.a[i + j] = temp;
            }
        }
        if (up != 0)
            ret.a[i + j] = up;
    }
    ret.len = i + j;
    while (ret.a[ret.len - 1] == 0 && ret.len > 1)
        ret.len--;
    return ret;
}
BigNum BigNum::operator / (const int & b) const//大数对一个整数进行相除运算
{
    BigNum ret;
    int i, down = 0;
    for (i = len - 1; i >= 0; i--){
        ret.a[i] = (a[i] + down * (MAXN + 1)) / b;
        down = a[i] + down * (MAXN + 1) - ret.a[i] * b;
    }
    ret.len = len;
    while (ret.a[ret.len - 1] == 0 && ret.len > 1)
        ret.len--;
    return ret;
}
int BigNum::operator % (const int & b) const//大数对一个int类型的变量进行取模运算
{
    int i, d = 0;
    for (i = len - 1; i >= 0; i--){
        d = ((d * (MAXN + 1)) % b + a[i]) % b;
    }
    return d;
}
BigNum BigNum::operator ^ (const int & n) const//大数的n次方运算
{
    BigNum t, ret(1);
    int i;
    if (n < 0)
        exit(-1);
    if (n == 0)
        return 1;
    if (n == 1)
        return *this;
    int m = n;
    while (m > 1){
        t = *this;
        for (i = 1; i << 1 <= m; i <<= 1){
            t = t * t;
        }
        m -= i;
        ret = ret * t;
        if (m == 1)
            ret = ret * (*this);
    }
    return ret;
}
bool BigNum::operator > (const BigNum & T) const//大数和另一个大数的大小比较
{
    int ln;
    if (len > T.len)
        return true;
    else if (len == T.len){
        ln = len - 1;
        while (a[ln] == T.a[ln] && ln >= 0)
            ln--;
        if (ln >= 0 && a[ln] > T.a[ln])
            return true;
        else
            return false;
    } else
        return false;
}
bool BigNum::operator > (const int & t) const//大数和一个int类型的变量的大小比较
{
    BigNum b(t);
    return *this > b;
}

void BigNum::print(){//输出大数
    int i;
    cout << a[len - 1];
    for (i = len - 2; i >= 0; i--){
        cout.width(DLEN);
        cout.fill('0');
        cout << a[i];
    }
    cout << endl;
}
int main(void){
    int i, n;
    BigNum x[101];//定义大数的对象数组
    x[0] = 1;
    for (i = 1; i < 101; i++)
        x[i] = x[i - 1] * (4 * i - 2) / (i + 1);
    while (scanf("%d", &n) == 1 && n != -1){
        x[n].print();
    }
}

 

简单模板

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>

#define LL long long
int const MAX = 1e6 + 1;
int const INF = 1 << 30;
double const EPS = 0.00000001;
using namespace std;
int const MAXLEN = 10000;

struct BigNum {
    //保存各个位数的值,由低位到高位
    char a[MAXLEN];
    int len;
    BigNum(){
        memset(a, 0, sizeof(a));
        len = 1;
    }
    //将一个int类型的变量转化为大数
    BigNum(int n){
        memset(a, 0, sizeof(a));
        len = 0;
        do {
            a[len++] = n % 10;
            n /= 10;
        } while (n);
    }
    //将一个字符串类型的变量转化为大数
    BigNum(const char* s){
        memset(a, 0, sizeof(a));
        //由低位到高位赋值
        len = strlen(s);
        for (int i = len - 1; i >= 0; i--)
            a[len - i - 1] = s[i] - '0';
    }
    //拷贝构造函数
    BigNum(const BigNum &bg){
        memset(a, 0, sizeof(a));
        len = bg.len;
        for (int i = 0; i < len; i++)
            a[i] = bg.a[i];
    }
//重载赋值运算符,大数之间进行赋值运算
    BigNum &operator = (const BigNum & bg){
        memset(a, 0, sizeof(a));
        len = bg.len;
        for (int i = 0; i < len; i++)
            a[i] = bg.a[i];
        return *this;
    }

    //重载加法运算符,两个大数之间的相加运算
    BigNum operator + (const BigNum &bg) const {
        BigNum nbg;
        int t = 0, maxlen = max(len, bg.len);//表示进位

        for (int i = 0; i < maxlen; i++){
            int sum = a[i] + bg.a[i] + t;
            nbg.a[i] = sum % 10;
            t = sum / 10;
        }

        if (t)
            nbg.a[maxlen++] = t;
        nbg.len = maxlen;
        return nbg;
    }
    //重载减法运算符,两个大数之间的相减运算
    BigNum operator - (const BigNum &) const;

    //重载乘法运算符,两个大数之间的相乘运算
    BigNum operator * (const BigNum &bg) const {
        BigNum nbg;
        int k = 0;//需要乘几次10
        for (int i = 0; i < len; i++){
            nbg.show();
            BigNum t = bg;
            for (int j = 0; j < k; j++)
                t = t * 10;
            nbg = nbg + t * a[i];
            k++;
        }
        nbg.show();
        return nbg;
    }

    //重载乘法运算符,大数 与int之间的相乘运算
    BigNum operator * (const int n) const {
        BigNum nbg;
        int nlen = len, t = 0;
        for (int i = 0; i < len; i++){
            t = a[i] * n + t;
            nbg.a[i] = t % 10;
            t /= 10;
        }
        while (t){
            nbg.a[nlen++] = t % 10;
            t /= 10;
        }
        nbg.len = nlen;
        return nbg;
    }
    //重载除法运算符,大数对一个整数进行相除运算
    BigNum operator / (const int   &) const {
        BigNum nbg;
        return nbg;
    }

    int operator % (const int& mod) const {
        int t = 0;
        for (int i = len - 1; i >= 0; i--){
            t = t * 10 + a[i];
            while (t < mod && i > 0)
                t = t * 10 + a[--i];

            if (t < mod) break;
            t = t % mod;
        }
        return t;
    }
    void show(){
        // printf("len=%d\n", len);
        for (int i = len - 1; i >= 0; i--)
            printf("%d", a[i]);
    }
};

char s1[MAXLEN], s2[MAXLEN];
int main(){
    int T;
    scanf("%d", &T);

    for (int c = 1; c <= T; c++){
        scanf("%s %s", s1, s2);
        BigNum n1(s1), n2(s2);
        BigNum n3 = n1 + n2;
        printf("Case %d:\n", c);
        n1.show();
        printf(" + ");
        n2.show();
        printf(" = ");
        n3.show();
        printf("\n");
        if (c != T)
            printf("\n");
    }

    return 0;
}

 

© 著作权归作者所有

共有 人打赏支持
粉丝 23
博文 1071
码字总数 721612
作品 0
西安
ACM Summer Training Warm up

ACM Summer Training Warm up Cover 热身水题 题目 HDU 4500 小Q系列故事——屌丝的逆袭 思路 简单的模拟,一个数组读入数据,一个数组计算维护结果 HDU 2109 Fighting for HDU 思路 简单排序...

SpiffyEight77
2017/08/14
0
0
【总结】DFS算法模板及题型分类

DFS算法模板及题型分类 题型分类: 写过这些入门题后,我们可以将DFS题分为两大类: 1 . 地图型:这种题型将地图输入,要求完成一定的任务。因为地图的存在。使得题意清楚形象化,容易理清搜...

chen_yuazzy
2017/07/31
0
0
HDU1002 A + B Problem II(修正版)

最近又开始做ACM题目了,昨天无意中翻阅自己写的一些blog,在07年写的一篇blog:http://www.cnblogs.com/phinecos/archive/2007/12/22/1011028.html,发现评论中有朋友报了一个bug,随手调试了下...

嗯哼9925
01/07
0
0
快速幂取模算法

Cover.jpg 前言 在算法程序设计竞赛中,我们竞赛选手会经常碰到对某个数N进行求大数次幂并对1e9+7取模的运算的题目,一方面求大数次幂是一个时间复杂度很高的运算(容易超时),另一方面对1...

SpiffyEight77
2017/12/08
0
0
Aho-Corasick automaton(AC自动机)解析及其在算法竞赛中的典型应用举例

摘要:   本文主要讲述了AC自动机的基本思想和实现原理,如何构造AC自动机,着重讲解AC自动机在算法竞赛中的一些典型应用。 什么是AC自动机? 如何构造一个AC自动机? AC自动机在算法竞赛中...

Reqaw
08/11
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

弹性工作制的魔咒

简评:你找到了一份完美的工作 —— 可以提前离开公司,还可以在晚上从家里回复邮件。既然如此,你为什么还会有那么强的负罪感呢? 或许是弹性工作制魔咒在作祟。 很多享受弹性工作制的人会始...

极光推送
5分钟前
0
0
KAFKA介绍(分布式架构)

Kafka是一个分布式的、可分区的、可复制的消息系统。它提供了普通消息系统的功能,但具有自己独特的设计。这个独特的设计是什么样的呢? 首先让我们看几个基本的消息系统术语: Kafka将消息以...

明理萝
11分钟前
0
1
os::NodeHandle::subscribe回调函数绑定对象

void Foo::callback(const std_msgs::Empty::ConstPtr& message){}Foo foo_object;ros::Subscriber sub = handle.subscribe("my_topic", 1, &Foo::callback, &foo_object); 参考: ht......

itfanr
12分钟前
0
0
React16.4 开发简书项目 从零基础入门到实战

React16.4 开发简书项目 从零基础入门到实战 关注我的订阅号下载 React16.4 开发简书项目 从零基础入门到实战

蜗牛奔跑
15分钟前
0
0
day57-20180815-流利阅读笔记-待学习

社恐怎么办?这个漫画或许能治愈你 毛西 2018-08-15 1.今日导读 近日,芬兰漫画家卡罗利娜·科尔霍宁创作的绘本《芬兰人的噩梦》在中国大火。一时间书中的主人公马蒂成为了人们茶余饭后热议的...

aibinxiao
19分钟前
3
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部