bignum.cpp (4)
Dưới đây là code bignum chỉ sử dụng hai biến long long. Code này dành cho những bài toán cần kiểu dữ liệu lớn hơn long long một chút.
Bài toán
Nhập n số nguyên dương (các số nhỏ hơn 10^20), sau đó tính tổng các số này và chia cho k. (1<=n<=1000, 1<=k<=20).
Độ phức tạp
tính tổng hai bignum : O(1)
chia bignum cho một int : O(1)
Code này của Nguyễn Tiến Trung Kiên
#include <stdio.h>
#include <string.h>
#define long long long
const long BASE = 1000000000LL * 1000000LL;
struct bigint {
long LO, HI;
void operator += (const bigint& A){
LO += A.LO; HI += A.HI;
HI += LO / BASE;
LO %= BASE;
}
void operator /= (int x){
LO += (HI % x) * BASE;
HI /= x;
LO /= x;
}
void operator = (int x){
HI = 0;
LO = x;
}
void load(){
char s[123];
scanf("%s", s);
int len = strlen(s);
if (len>15) {
sscanf(s+len-15, "%lld", &LO);
s[len-15] = 0;
sscanf(s, "%lld", &HI);
}
else {
HI = 0;
sscanf(s, "%lld", &LO);
}
}
void show(){
if (HI==0) printf("%lld", LO);
else printf("%lld%015lld", HI, LO);
}
};
bigint A, S;
main(){
int n, k, i, t;
for (t=1; t<=1000111000; t++){
scanf("%d%d", &n, &k);
if (k==0) return 0;
S = 0;
for (i=1; i<=n; i++){
A.load();
S += A;
}
printf("Bill #%d costs ", t);
S.show();
printf(": each friend should pay ");
S /= k;
S.show();
printf("\n\n");
}
}
Nhận xét
Code trên kia sử dụng hệ cơ số 10^15.
Bignum này có khả năm lưu đưuọc các giá trị từ 0 đến 10^33. (18 chữ số ở biến HI, 15 chữ số ở biến LO)
Tổng lớn nhất của bài toán có thể đạt được là 10^23.
Yêu cầu chia cho số k nhưng k khác bé (1<=k<=20), vậy thao tác có nhớ khi chia (LO += (HI % x) * BASE) không bị tràn.
Vậy nên nếu k lớn hơn một chút nữa thì ta phải giảm hệ cơ số.
Mô tả
hàm load() : đọc một bignum từ bàn phím
hàm show() : hiển thị bignum ra màn hình