在我实现的高精度里,为什么输入 21 7 会输出 613566759?
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll yh = 1e3;
#define BASE 1000000000
class uints{
public:
vector<int> d;
void clear0(){
while (!this->d.empty() && !this->d.back()) this->d.pop_back();
if (this->d.empty()) this->d.push_back(0);
}
uints(): d(1, 0){}
uints(int _int){
if (!_int){this->d.push_back(0); return;}
while (_int > 0) this->d.push_back(_int % BASE), _int /= BASE;
}
uints(const string& _string){
int l, tmp;
for (int r = _string.size() - 1; r >= 0; r -= 9){
if (r >= 9) l = r - 8;
else l = 0;
tmp = 0;
for (int i = l; i <= r; i++) tmp = tmp * 10 + _string[i] - '0';
this->d.push_back(tmp);
}
}
bool operator == (const uints& that) const{
if (this->d.size() != that.d.size()) return 0;
for (int i = 0; i < this->d.size(); i++) if (this->d[i] != that.d[i]) return 0;
return 1;
}
bool operator < (const uints& that) const{
if (this->d.size() != that.d.size()) return this->d.size() < that.d.size();
for (int i = this->d.size() - 1; i >= 0; i--) if (this->d[i] != that.d[i]) return this->d[i] < that.d[i];
return 0;
}
bool operator > (const uints& that) const{return that < *this;}
bool operator <= (const uints& that) const{return !(that < *this);}
bool operator >= (const uints& that) const{return !(*this < that);}
uints operator + (const uints& that) const{
uints res;
res.d.resize(max(this->d.size(), that.d.size()) + 1);
int tmp = 0;
for (int i = 0; i < res.d.size(); i++){
int ans = tmp;
if (i < this->d.size()) ans += this->d[i];
if (i < that.d.size()) ans += that.d[i];
res.d[i] = ans % BASE;
tmp = ans / BASE;
}res.clear0();
return res;
}
uints operator - (const uints& that) const{
uints res = *this;
bool f = 0;
for (int i = 0; i < res.d.size(); i++){
int ans = res.d[i] - f;
if (i < that.d.size()) ans -= that.d[i];
if (ans < 0) ans += BASE, f = 1;
else f = 0;
res.d[i] = ans;
}res.clear0();
return res;
}
uints operator * (const uints& that) const{
uints res;
res.d.resize(this->d.size() + that.d.size());
for (int i = 0; i < this->d.size(); i++){
int tmp = 0;
for (int j = 0; j < that.d.size() || tmp > 0; j++){
int ans = res.d[i + j] + tmp;
if (j < that.d.size()) ans += this->d[i] * that.d[j];
res.d[i + j] = ans % BASE;
tmp = ans / BASE;
}
}res.clear0();
return res;
}
uints operator / (const uints& that) const{
if (*this < that) return uints(0);
uints res, _res;
for (int i = this->d.size() - 1; i >= 0; i--){
_res = _res * BASE + this->d[i];
int ans = 0, l = 0, r = BASE - 1, mid;
while (l <= r){
mid = l + r >> 1;
if (that * mid <= _res) l = mid + 1, ans = mid;
else r = mid - 1;
}res.d.push_back(ans);
_res = _res - that * ans;
}reverse(res.d.begin(), res.d.end());
res.clear0();
return res;
}
uints& operator -- (){return *this = *this - 1;}
bool check(uints a){
if (a.d.size() * 2 - 1 > this->d.size()) return 0;
if (*this >= a * a) return 1;
return 0;
}
uints sqrt(){
uints l, r, mid, ans;
l = 1, r = *this;
while (l <= r){
mid = (l + r) / 2;
if (this->check(mid)){
if (mid >= ans) ans = mid;
l = mid + 1;
}else r = mid - 1;
}return ans;
}
};
istream& operator >> (istream& _i, uints& _uints){
string _string;
_i >> _string;
_uints = uints(_string);
return _i;
}
ostream& operator << (ostream& _o, const uints& _uints){
if (_uints.d.empty()){_o << 0; return _o;}
_o << _uints.d.back();
for (int i = _uints.d.size() - 2; i >= 0; i--){
for (int k = BASE / 10; _uints.d[i] < k; k /= 10) cout << '0';
if (_uints.d[i]) cout << _uints.d[i];
}return _o;
}
/*
uints _gcd(uints __m, uints __n){
if (__n == uints(0)) return __m;
cerr<<"(__n,__m-uints(__m/__n)*__n)=("
<<__n<<","<<__m<<"-uints("<<uints(__m/__n)<<")*"<<__n<<")=("
<<__n<<","<<__m-uints(__m/__n)*__n<<")\n";
return _gcd(__n, __m - uints(__m / __n) * __n);
}
uints YH[yh + 1][yh + 1] = {{uints("0"), uints("1")}};
*/
//---
signed main(){
uints a,b;
cin >>a>>b;
cout<<uints(a/b);
// for (ll i = 1; i <= 10; i++){
// for (ll j = 1; j <= i; j++) YH[i][j] = YH[i - 1][j - 1] + YH[i - 1][j];
//// for (ll j = 3; j <= i + 1 >> 1; j++) cout << YH[i][j] << ' ';
//// cout << '\n';
// uints gcd;
// gcd = YH[i][2];
//// for (ll j = 3; j < i; j++) if (YH[i][j] < 0){
//// cerr<<"<0";
//// exit(-1);
//// }
// cout << gcd;
// for (ll j = 3; j <= i + 1 >> 1; j++) gcd = _gcd(gcd, YH[i][j]), cout << ' ' << gcd;
//// cout << i << ':' << gcd << '\t';
// cout << '\n';
// }
return 0;
}
dalao 们,哪儿错了?