c + + 대수 클래스
8284 단어 데이터 구조 템 플 릿
#include
#include
#include
#include
#define LL long long
#define INF 0x3f3f3f3f
using namespace std;
const int M = 1e3+10;
const int MAXN = 9;
class BigNum {
public:
int a[M],len,sign;
void init();
void assignString(const char*);
void assignInt(LL);
LL toInt()const;
BigNum();
BigNum(LL);//int -> BigNum
BigNum(const char*);//char -> BigNum
BigNum(const BigNum &); //BigNum = BigNum
BigNum &operator = (const BigNum &);
friend istream& operator>>(istream&,BigNum&);
friend ostream& operator< (const BigNum&)const;
bool operator < (const BigNum&)const;
BigNum operator + (const LL&)const;//all
BigNum operator - (const LL&)const;//all
BigNum operator * (const LL&)const;//all
BigNum operator / (const LL&)const;//LL != 0 && BigNum all
BigNum operator ^ (const LL&)const;//LL >= 0 && BigNum >= 0
LL operator % (const LL&)const;//BigNum >=0 && LL > 0
};
void BigNum::init() {
len = 0;
sign = 1;
memset(a,0,sizeof(a));
}
void BigNum::assignString(const char *s) {
init();
int l = strlen(s);
int k = 0;
if(s[0] == '-') {
sign = -1;
k++;
}
int j = 0;
for(LL seed = 1; seed < MAXN; seed *= 10,j++) ;
bool flag = false;
for(int i = l-1; i >= k; i -= j) {
for(int jj = max(i-j+1,k); jj <= i; ++jj) {
a[len] = a[len]*10+(s[jj]-'0');
}
len++;
if(a[len-1] != 0) {
flag = true;
}
}
if(!flag) {
sign = 1;
len = 1;
}
}
void BigNum::assignInt(LL b) {
init();
if(b == 0) {
len = 1;
return ;
}
if(b < 0) {
sign = -1;
b = -b;
}
while(b) {
a[len++] = b%(MAXN+1);
b /= (MAXN+1);
}
}
LL BigNum::toInt() const{
LL res = 0,seed = 1;
for(int i = len-1; i >= 0; --i) {
res += seed*res+a[i];
seed *= (MAXN+1);
}
if(sign == -1) res = -res;
return res;
}
BigNum::BigNum() {
init();
len = 1;
}
BigNum::BigNum(LL b) {
assignInt(b);
}
BigNum::BigNum(const char* s) {
assignString(s);
}
BigNum::BigNum(const BigNum& t){
*this = t;
}
BigNum & BigNum::operator = (const BigNum & t) {
init();
len = t.len;
sign = t.sign;
for(int i = 0; i < t.len; ++i) {
a[i] = t.a[i];
}
return *this;
}
istream& operator >> (istream& in,BigNum &t) {
char s[M];
in>>s;
t.assignString(s);
return in;
}
ostream& operator << (ostream& ou,BigNum &t) {
if(t.sign == -1){
ou<= 0; --i) {
ou.width(j);
ou.fill('0');
ou< len ? t.len : len;
for(int i = 0; i < big; ++i) {
res.a[i] += t.a[i];
if(res.a[i] > MAXN) {
res.a[i+1]++;
res.a[i] -= MAXN+1;
}
}
if(res.a[big] != 0) {
res.len = big+1;
}
else {
res.len = big;
}
}
else if(sign == 1 && t.sign == -1) {
BigNum tmp(t);
tmp.sign = 1;
res = *this-tmp;
}
else {
BigNum tmp(*this);
tmp.sign = 1;
res = t-tmp;
}
return res;
}
BigNum BigNum::operator - (const BigNum &t)const {
BigNum res;
if(sign == t.sign && sign == 1) {
BigNum t1,t2;
if(*this < t) {
t1 = t;
t2 = *this;
t1.sign = -1;
}else {
t1 = *this;
t2 = t;
}
int big = t1.len;
for(int i = 0; i < big; ++i) {
if(t1.a[i] < t2.a[i]) {
int 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];
}
}
while(t1.a[t1.len-1] == 0 && t1.len > 1) {
t1.len--;
}
if(t1.len == 1 && t1.a[0] == 0){
t1.sign = 1;
}
res = t1;
}
else if(sign == t.sign && sign == -1){
BigNum t1,t2;
t1 = t;
t2 = *this;
t1.sign = t2.sign = 1;
res = t1-t2;
}
else if(sign == 1 && t.sign == -1) {
BigNum t1,t2;
t1 = *this;
t2 = t;
t2.sign = 1;
res = t1+t2;
}
else if(sign == -1 && t.sign == 1) {
BigNum t1,t2;
t1 = *this;
t2 = t;
t2.sign = -1;
res = t1+t2;
}
return res;
}
BigNum BigNum::operator * (const BigNum &t)const {
BigNum res;
res.sign = sign*t.sign;
int i,j;
for(i = 0; i < len; ++i) {
int up = 0;
for(j = 0; j < t.len; ++j) {
int tmp = a[i]*t.a[j]+res.a[i+j]+up;
if(tmp > MAXN) {
int tmp1 = tmp - tmp/(MAXN+1)*(MAXN+1);
up = tmp / (MAXN+1);
res.a[i+j] = tmp1;
}else {
up = 0;
res.a[i+j] = tmp;
}
}
if(up != 0) {
res.a[i+j] = up;
}
}
res.len = i+j;
while(res.a[res.len-1] == 0 && res.len > 1) {
res.len--;
}
if(res.len == 1 && res.a[0] == 0){
res.sign = 1;
}
return res;
}
BigNum BigNum::operator / (const BigNum &t)const {
LL b = t.toInt();
BigNum res = *this/b;
return res;
}
BigNum BigNum::operator + (const LL& b)const {
BigNum t(b);
BigNum res = *this+t;
return res;
}
BigNum BigNum::operator - (const LL& b)const {
BigNum t(b);
BigNum res = *this-t;
return res;
}
BigNum BigNum::operator * (const LL& b)const {
BigNum t(b);
BigNum res = *this*t;
return res;
}
BigNum BigNum::operator / (const LL& b)const {
BigNum res;
BigNum t1(*this),t2(b),t3(b);
t1.sign = t2.sign = 1;
if(t1 < t2) {
res.assignInt(0);
}else {
res.sign = sign*t3.sign;
LL bb = abs(b);
int down = 0;
for(int i = len-1; i >= 0; --i) {
res.a[i] = (a[i]+down*(MAXN+1))/bb;
down = a[i]+down*(MAXN+1)-res.a[i]*bb;
}
res.len = len;
while(res.a[res.len-1] == 0 && res.len > 1) {
res.len--;
}
}
return res;
}
BigNum BigNum::operator ^ (const LL& b)const {
BigNum res(1);
if(b != 0) {
BigNum seed(*this);
LL bb = b;
while(bb) {
if(bb & 1) {
res = res*seed;
}
bb >>= 1;
seed = seed*seed;
}
}
return res;
}
LL BigNum::operator % (const LL& b)const {
LL d = 0;
for(int i = len-1; i >= 0; --i) {
d = ((d*(MAXN+1))%b+a[i])%b;
}
return d;
}
//>= 1
bool BigNum::operator > (const BigNum &t)const {
if(sign > t.sign || len > t.len) {
return true;
}
if(sign < t.sign || len < t.len) {
return false;
}
bool flag = sign==-1?false:true;
for(int i = len-1; i >= 0; --i) {
if(a[i] < t.a[i]) {
if(flag) return false;
return true;
}
if(a[i] > t.a[i]) {
if(flag) return true;
return false;
}
}
return true;
}
//< 1
bool BigNum::operator < (const BigNum &t)const {
return !(*this > t);
}
int main() {
char ch[1000];
LL b,c;
while(~scanf("%lld%lld",&b,&c)) {
BigNum bn1(b);
BigNum bn2(c);
BigNum bn3 = bn1/c;
LL d = b/c;
cout<