高精度模板 洛谷Luogu P1932 A+B & A-B & A*B & A/B Problem
2024-10-07 12:09:05
P1932 A+B & A-B & A*B & A/B Problem
题目背景
这个题目很新颖吧！！！
题目描述
求A、B的和差积商余！
输入输出格式
输入格式：
两个数两行
A B
输出格式：
五个数
和 差 积 商 余
输入输出样例
输入样例#1：
1
1
输出样例#1：
2
0
1
1
0
说明
length(A),length(B)<=10^4
每个点3s。
题目链接
很明显，这道题是一道模板题，是很明显的高精度算法。当我翻阅《算法竞赛入门经典（第二版）》时，帅气的汝佳哥告诉我在代码仓库中有减法、乘法、除法的代码，但是当我来到代码仓库时，却被眼前的景象惊呆了
并没有什么减乘除！！
那这简直是一把鼻涕一把眼泪啊！还要自己思考、自己想算法。没办法，于是打了一份模板（调试了好久啊喂(╯‵□′)╯︵┻━┻）。但可怕的是，发生了如下情况：
七十分代码：[真正的模板]
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
#include<cmath>
#define ll long long
#define INF 2147483647
#define ll_INF 9223372036854775807
using namespace std;
struct BigInteger {
static const int BASE = 10000;
static const int WIDTH = 4;
int size, s[11000];
inline void killzero() {
while( s[size - 1] == 0 && size > 1 ) size --;
}
inline void clear() {
size = 0; s[0] = 0;
}
inline void reverse() {
for( int i = 0 ; i < size >> 1 ; ++ i ) swap( s[i], s[size - i - 1] );
}
BigInteger( long long num = 0 ) { *this = num; }
BigInteger operator = ( long long num ) {
clear();
do {
s[size ++] = num % BASE;
num /= BASE;
} while( num > 0 );
return *this;
}
BigInteger operator = ( const string &str ) {
clear();
int x, len = ( str.length() - 1 ) / WIDTH + 1;
for( int i = 0 ; i < len ; ++ i ) {
int end = str.length() - i * WIDTH;
int start = max( 0, end - WIDTH );
sscanf( str.substr( start, end - start ).c_str(), "%d", &x );
s[size ++] = x;
}
return *this;
}
BigInteger operator + ( const BigInteger &b ) const {
BigInteger c;
c.clear();
for( int i = 0, g = 0 ; ; ++ i ) {
if( g == 0 && i >= size && i >= b.size ) break;
int x = g;
if( i < size ) x += s[i];
if( i < b.size ) x += b.s[i];
c.s[c.size ++] = x % BASE;
g = x / BASE;
}
c.killzero();
return c;
}
BigInteger operator - ( const BigInteger &b ) const {
BigInteger c;
c.clear();
for( int i = 0, g = 0 ; ; ++ i ) {
if( g == 0 && i >= size && i >= b.size ) break;
int x = -g;
if( i < size ) x += s[i];
if( i < b.size ) x -= b.s[i];
g = 0;
while( x < 0 ) { x += BASE ; ++ g; }
c.s[c.size ++] = x;
}
while( c.s[c.size - 1] == 0 && c.size > 1 ) c.size --;
return c;
}
BigInteger operator * ( const BigInteger &b ) const {
BigInteger c;
c.clear();
for( int i = 0 ; i < b.size ; ++ i ) {
BigInteger t;
t.clear();
if( b.s[i] == 0 ) continue;
for( int j = 0, g = 0 ; j < size || g != 0; ++ j ) {
int x = g;
if( j < size ) x += b.s[i] * s[j];
t.s[t.size ++] = x % BASE;
g = x / BASE;
}
BigInteger tmp;
tmp.clear();
for( int j = 0, g = 0 ; ; ++ j ) {
if( g == 0 && j >= t.size + i && j >= c.size ) break;
int x = g;
if( j < c.size ) x += c.s[j];
if( j >= i && j < t.size + i ) x += t.s[j - i];
tmp.s[tmp.size ++] = x % BASE;
g = x / BASE;
}
c = tmp;
}
c.killzero();
return c;
}
BigInteger operator / ( const BigInteger &b ) const {
BigInteger c, t;
c.clear(); t.clear();
for( int i = size - 1 ; i >= 0 ; -- i ) {
t = t * BASE + s[i];
int x = 0;
while( b <= t ) { t -= b; x ++ ; }
c.s[c.size ++] = x;
}
c.reverse();
c.killzero();
return c;
}
BigInteger operator % ( const BigInteger &b ) const {
BigInteger c;
c.clear();
for( int i = size - 1 ; i >= 0 ; -- i ) {
c = c * BASE + s[i];
while( b <= c ) c -= b;
}
c.killzero();
return c;
}
BigInteger operator += ( const BigInteger &b ) {
*this = *this + b;
return *this;
}
BigInteger operator -= ( const BigInteger &b ) {
*this = *this - b;
return *this;
}
BigInteger operator *= ( const BigInteger &b ) {
*this = *this * b;
return *this;
}
BigInteger operator /= ( const BigInteger &b ) {
*this = *this / b;
return *this;
}
BigInteger operator %= ( const BigInteger &b ) {
*this = *this % b;
return *this;
}
BigInteger operator ++ () {
*this = *this + 1;
return *this;
}
BigInteger operator ++ (int) {
BigInteger old = *this;
++ (*this);
return old;
}
BigInteger operator -- () {
*this = *this - 1;
return *this;
}
BigInteger operator -- (int) {
BigInteger old = *this;
++ (*this);
return old;
}
bool operator < ( const BigInteger &b ) const {
if( size != b.size ) return size < b.size;
for( int i = size - 1 ; i >= 0 ; -- i )
if( s[i] != b.s[i] ) return s[i] < b.s[i];
return false;
}
bool operator > ( const BigInteger &b ) const { return b < *this; }
bool operator <= ( const BigInteger &b ) const { return !( b < *this ); }
bool operator >= ( const BigInteger &b ) const { return !( *this < b ); }
bool operator != ( const BigInteger &b ) const { return b < *this || *this < b ;}
bool operator == ( const BigInteger &b ) const { return !( b < *this ) && !( *this < b ); }
void read() {
clear();
char s1[11000];
scanf( "%s", s1 );
int x, len_of_s1 = strlen( s1 ), rem = len_of_s1 % WIDTH , point = 1 - WIDTH;
for( int i = len_of_s1 - 1 ; i >= rem ; -- i ) {
x = x * 10 + s1[i + point] - '0'; point += 2;
if( ( len_of_s1 - i ) % WIDTH == 0 ) { s[size ++] = x; x = 0; point = 1 - WIDTH; }
}
if( rem != 0 ){
int x = 0;
for( int i = 0 ; i < rem ; ++ i ) x = x * 10 + s1[i] -'0';
s[size ++] = x;
}
}
void writeln() {
printf( "%d", s[size - 1] );
for(int i = size - 2 ; i >= 0 ; -- i ) printf( "%04d", s[i] );
putchar( '\n' );
}
};
BigInteger A, B;
int main(){
A.read(); B.read();
BigInteger add = A + B, cut = max( A, B ) - min( A, B ), mul = A * B, div = A / B, rem = A % B;
add.writeln(); cut.writeln(); mul.writeln(); div.writeln(); rem.writeln();
return 0;
}
为什么只有七十分？思考之后才发现，其实在做高精度除法的时候，就可以顺带着输出余数，这样才能真好踩着时间点过。
运行截图：
代码：（主程序）
BigInteger A, B;
int main(){
A.read(); B.read();
BigInteger add = A + B, cut = max( A, B ) - min( A, B ), mul = A * B;
add.writeln(); cut.writeln(); mul.writeln();
BigInteger c, t;
c.clear(); t.clear();
for( int i = A.size - 1 ; i >= 0 ; -- i ) {
t = t * BigInteger::BASE + A.s[i];
int x = 0;
while( B <= t ) { t = t - B; x ++ ; }
c.s[c.size ++] = x;
}
for( int i = 0 ; i <= ( c.size - 1 ) >> 1 ; ++ i ) swap( c.s[i], c.s[c.size - i - 1] );
while( c.s[c.size - 1] == 0 && c.size > 1 ) c.size --;
c.writeln(); t.writeln();
return 0;
}
最新文章
- mysql下载安装
- 【JMS】JMS之ActiveMQ的使用
- Java提高篇——equals()方法和“==”运算符
- NOIP 2015复赛提高组Day2 T1==Codevs 4768 跳石头
- 【POJ 2987】Firing （最小割-最大权闭合子图）
- Entify Framewrok - 学习链接
- c3p0链接池
- Spring源代码由浅入深系列五 GetBean
- android 关于LCD背光调节渐变过程引起背光闪烁问题
- j2ee面试宝典翻译(3) j2ee job interview companion
- 如何写好git commit message
- 在Python中进行JSON转化
- AJAX使用说明书
- Confluence 6 如何备份存储文件和页面信息
- sku 和 spu
- (转)Python3之requests模块
- 2333: [SCOI2011]棘手的操作[离线线段树]
- KnockoutJs学习笔记（一）
- 【CodeForces】932 E. Team Work
- 第5堂音频课：发音&词串&自学方法示范