@[buaa_czx](/user/90036) 比较没去前导0?
by Killer_joke @ 2023-01-27 15:22:55
@[Killer_joke](/user/915814) 试过比较前去除前导零了,应该不是前导零的问题,而且前导零也解释不通hack数据
qwq调了快三个小时了
by buaa_czx @ 2023-01-27 15:30:14
新增亿些hack数据:
101~109 2
1001~1099 2
....
100000001 2
诸如此类,望大佬解惑qwq
by buaa_czx @ 2023-01-27 15:34:06
高精度大可不必这样写 我一般都用字符串或数组实现的
by hjqhs @ 2023-01-27 15:35:58
```cpp
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<string>
#include<vector>
using namespace std;
void clear_0(vector<long long>& a) { //清除前导零
while(a.back()==0&&a.size()>1) {
a.pop_back();
}
return ;
}
void carry(vector<long long>& a) { //进位
for(int i=0; i<a.size(); i++) {
if(i==a.size()-1) {
if(a[i]>9) {
a.push_back(a[i]/10);
a[i]%=10;
}
} else {
a[i+1]+=a[i]/10;
a[i]%=10;
}
}
return;
}
void add(vector<long long>& num,int i,long long a) { //num[i]+=a
if(i<num.size()) num[i]+=a;
else {
num.push_back(a);
}
return ;
}
struct bigint {
vector<long long> num;
bigint operator=(const long long aa) {//重载赋值运算符=,用long long赋值bigint
long long a=aa;
if(a==0) {
this->num.push_back(0);
}
while(a!=0) {
this->num.push_back(a%10);
a/=10;
}
clear_0(this->num);
return (*this);
}
bigint operator=(const string s) {//重载赋值运算符=,用string赋值bigint
for(int i=s.length()-1; i>=0; i--) {
this->num.push_back(s[i]-'0');
}
clear_0(this->num);
return (*this);
}
bool operator<(const bigint a)const{
if(this->num.size()!=a.num.size()){
return this->num.size()<a.num.size();
}
for(int i=a.num.size()-1;i>=0;i--){
if(this->num[i]!=a.num[i]) return this->num[i]<a.num[i];
}
return false;
}
bool operator>(const bigint a)const{
return a<*this;
}
bool operator==(const bigint a)const{
return !(*this<a)&&!(a<*this);
}
bool operator>=(const bigint a)const{
return *this>a||a==*this;
}
bool operator<=(const bigint a)const{
return *this<a||a==*this;
}
bigint operator+(const bigint a) {//高精度加法,bigint+bigint
bigint ans;
ans.num.clear();
int l=max(a.num.size(),this->num.size());
for(int i=0; i<l; i++) {
int x,y;
if(i<a.num.size()) x=a.num[i];
else x=0;
if(i<this->num.size()) y=this->num[i];
else y=0;
ans.num.push_back(x+y);
}
carry(ans.num);
clear_0(ans.num);
return ans;
}
bigint operator+(const long long aa) {
bigint a;
a=aa;
return a+(*this);
}
bigint operator*(const bigint a) { //高精度乘法,bigint*bigint
bigint ans;ans.num.clear();
for(int i=0; i<this->num.size(); i++)
for(int j=0; j<a.num.size(); j++) {
add(ans.num,i+j,this->num[i]*a.num[j]);
}
carry(ans.num);
clear_0(ans.num);
return ans;
}
bigint operator*(const long long a) { //高精度乘法,bigint*int
bigint ans;ans.num.clear();
for(int i=0; i<this->num.size(); i++) {
add(ans.num,i,a*this->num[i]);
}
carry(ans.num);
clear_0(ans.num);
return ans;
}
bigint operator+=(const bigint a) {
*this=(*this)+a;
return (*this);
}
bigint operator/(const long long a){
bigint ans;ans.num.clear();
long long x=0;
for(int i=this->num.size()-1;i>=0;i--){
x=x*10+this->num[i];
ans.num.push_back(x/a);
x%=a;
}
for(int i=0,j=ans.num.size()-1;i<j;i++,j--){
swap(ans.num[i],ans.num[j]);
}
clear_0(ans.num);
return ans;
}
bigint operator/(bigint a){
long long l=0,r=1e10,m;
bigint ans;ans.num.clear();
while(l<=r){
bigint m0,m1,m2;
m=(l+r)/2;m0=m;
m1=a*m0;m2=m1+a;
if((m1<=(*this))&&m2>(*this)) break;
else if(m2<=*this) l=m+1;
else r=m-1;
}
ans=m;
return ans;
}
};
istream& operator >> (istream& in,bigint& a) {
string s;
in>>s;
a=s;
clear_0(a.num);
return in;
}
ostream& operator<<(ostream& out,bigint& a) {
clear_0(a.num);
while((a.num.size()!=0)) {
out<<a.num.back();
a.num.pop_back();
}
return out;
}
int main() {
bigint a,c,b;
cin>>a>>b;
c=a/b;
cout<<c;
return 0;
}
```
改过了,您进位写错了@[buaa_czx](/user/90036)
by Killer_joke @ 2023-01-27 16:17:13
@[Killer_joke](/user/915814) 谢谢哥!!orz orz
确实进位的时候考虑欠妥了...当时拿这个大模板把高精度乘法加法也过了,所以完全没考虑到是乘法进位有问题~~(数据果然太水了~~
感谢感谢
by buaa_czx @ 2023-01-27 19:29:52