文档章节

hdu 1002 大数模板

 阿豪boy
发布于 2017/09/08 23:40
字数 1834
阅读 13
收藏 0
点赞 0
评论 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;
}

 

© 著作权归作者所有

共有 人打赏支持
粉丝 21
博文 881
码字总数 631558
作品 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

HDOJ 1002 A + B Problem II (Big Numbers Addition)

题目链接在此☞http://acm.hdu.edu.cn/showproblem.php?pid=1002 这题也比较简单,只需要开三个长度为1000的char数组来分别储存a、b、ans,再利用我们加法的算法,先向右对齐再相加。注意一下...

不高不富不帅的陈政_ ⋅ 2015/08/08 ⋅ 1

【总结】DFS算法模板及题型分类

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

chen_yuazzy ⋅ 2017/07/31 ⋅ 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

快速幂取模算法

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

SpiffyEight77 ⋅ 2017/12/08 ⋅ 0

Smarty模板引擎全教程

Smarty模板引擎全教程 前面已经介绍了在SpeedPHP框架中使用Smarty模板引擎的方法,下面我们来更详细地介绍Smarty的使用方法。 本章是对Smarty常用的一些功能进行了详述,让您在最短的时间内掌...

云栖希望。 ⋅ 2017/12/10 ⋅ 0

【日更】矩阵方面的各种习题?

恩……大二小萌新。 老板说要开始系统的学算法了呢恩……。 我先把之前开的矩阵习题做完再说别的好了。 然后后面可能会有一些最近刚出的题……2017年的icpc什么的。 打算停止更新啦……需要用...

s_amsara ⋅ 2017/11/06 ⋅ 0

ACM竞赛路上亲爱的坑们

写在前边:这些梗都是敝人自己做题和比赛时曾经坑过自己的地方,特别在这里记录一下,所有的链接都是本博客中的题解链接(有大致题意说明和代码),原题请到OJ上自行寻找。目的是提升自身姿势...

calabash_boy ⋅ 2017/08/02 ⋅ 0

hdu 1086线段相交模板

考虑情况要全面 http://acm.hdu.edu.cn/showproblem.php?pid=1086 code: #include <iostream> include "cstdio" include "cmath" include "algorithm" using namespace std;struct point{dou......

洛伊佩拉 ⋅ 2013/12/12 ⋅ 0

总结——Java大数模板应用

Java大数模板应用 在处理高精度问题和大数问题中,long long和double已经存不下了,比起在C++中自己用String手写运算过程,Java中的BigInteger类和BigDecimal类用起来就很方便了 0.创建大数类...

xp731574722 ⋅ 2017/11/02 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

Java集合类总结笔记

一、集合类的层次关系 主要容器集合类的特点: ArrayList 一种可以动态增长和缩减的索引序列 LinkedList 一种可以在任何位置进行高效地插入和删除的有序序列 ArrayDeque 一种用循环数组实现的...

edwardGe ⋅ 8分钟前 ⋅ 0

spring RMI远程调用

RMI https://www.cnblogs.com/wdh1995/p/6792407.html

BobwithB ⋅ 13分钟前 ⋅ 0

Jenkins实践2 之基本配置

1 插件管理 系统管理->插件管理 在可选插件中可以自主安装插件 2 管理用户 系统管理->管理用户->新建用户 3 安全配置 系统管理->全局安全配置 授权策略 选择安全矩阵 然后添加现有的用户,赋...

晨猫 ⋅ 13分钟前 ⋅ 0

c++智能指针

1、是一种泛型类,针对指针类型的泛型类,会保存指针 2、重载了符号 *和-> 对智能指针使用这两个符号,相当于对保存的泛型使用这两个符号 3、当智能指针引用计数为0时,会去释放指针指向的资...

国仔饼 ⋅ 14分钟前 ⋅ 0

Spring Boot错误处理机制

1)、SpringBoot默认的错误处理机制 默认效果: 1)、浏览器,返回一个默认的错误页面 浏览器发送请求的请求头: 2)、如果是其他客户端,默认响应一个json数据 原理: 可以参照ErrorMvcAut...

小致dad ⋅ 15分钟前 ⋅ 0

ftp连接不上的终极办法 SFTP

假如FTP由于各种原因就是连不上,那么用SFTP协议吧,使用登录服务器的账号密码。

sskill ⋅ 20分钟前 ⋅ 0

Unity 围绕旋转角度限制(Transform.RotateAround)

在 Unity 中可以利用 Transform.RotateAround 围绕指定物体进行旋转,但某些情况下可能需要对旋转角度进行控制。我是先计算出预设角度大小,然后判断是否在限定角度范围内是则进行旋转。 相关...

大轩 ⋅ 21分钟前 ⋅ 0

阿里沙箱环境支付宝测试demo

阿里支付宝支付和微信支付,包括:阿里沙箱环境支付宝测试demo,支付宝支付整合到spring+springmvc+mybatis环境和微信整合到如上环境,功能非常齐全,只需要修改对应的配置文件即可,帮助文档...

码代码的小司机 ⋅ 24分钟前 ⋅ 0

JDK1.6和JDK1.7中,Collections.sort的区别,

背景 最近,项目正在集成测试阶段,项目在服务器上运行了一段时间,点击表格的列进行排序的时候,有的列排序正常,有的列在排序的时候,在后台会抛出如下异常,查询到不到数据,而且在另外一...

tsmyk0715 ⋅ 41分钟前 ⋅ 0

C++ 中命名空间的 5 个常见用法

相信小伙伴们对C++已经非常熟悉,但是对命名空间经常使用到的地方还不是很明白,这篇文章就针对命名空间这一块做了一个叙述。 命名空间在1995年被引入到 c++ 标准中,通常是这样定义的: 命名...

柳猫 ⋅ 45分钟前 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部