提交记录 5884


用户 题目 状态 得分 用时 内存 语言 代码长度
orbitingfIea 1005a. 【模板题】高精度除法 Accepted 100 95.695 ms 148 KB C++11 7.00 KB
提交时间 评测时间
2018-09-06 09:56:01 2020-08-01 00:35:47

#include<bits/stdc++.h>
using namespace std;

class Bignum{
private:
  vector<int>a;
  void clear(){a.resize(1);a[0]=0;}
  void set_(int n){
    if(clear(),n){			
      int t;a.clear();
      while(n)a.push_back(n-(t=n/10000)*10000),n=t;
    }
  }
  void set_(long long n){
    if(clear(),n){			
      long long t;a.clear();
      while(n)a.push_back(n-(t=n/10000)*10000),n=t;
    }
  }
  void clearzero(){
    int l=a.size();
    while(l>1 && a[l-1]==0)l--;
    a.resize(l);
  }
  void set_(char*st){
    char c;vector<int> s;a.clear();
    while(((c=*(st++))<'0' || c>'9'));s.push_back(c-'0');
    while((c=*(st++))>='0'&&c<='9')s.push_back(c-'0');          
    int l=s.size();
    for (int i=l-1;i-3>=0;i-=4)a.push_back(s[i]+s[i-1]*10+s[i-2]*100+s[i-3]*1000);
    if(l&3){
      int tmp=0;
      for (int i=0;i<(l&3);i++)tmp=tmp*10+s[i];
      a.push_back(tmp);
    }
    clearzero();
  }
public:
  Bignum(){clear();}
  Bignum(int n){set_(n);}
  Bignum(long long n){set_(n);}
  Bignum(char*s){set_(s);}
  Bignum& operator=(int a){set_(a);return *this;}
  Bignum& operator=(long long a){set_(a);return *this;}
  Bignum& operator=(char *s){set_(s);return *this;}
  int size()const{
    if(a.back()>=1000)return a.size()<<2;
    else if(a.back()>=100)return (a.size()<<2)-1;
    else if(a.back()>=10)return (a.size()<<2)-2;
    else return (a.size()<<2)-3;
  }
  long long toint()const{
    long long ans=0;
    for (int i=int(a.size())-1;i>=0;i--)ans=ans*10000+a[i];
    return ans;
  }
  int tostr(char *s)const{
    int tot=0;
    for (unsigned int i=0;i<a.size();i++)
      if(i+1==a.size()){
        int x=a[i];
        while(x)s[tot++]='0'+x%10,x/=10;
      }else{
        int x=a[i];
        for (int j=0;j<4;j++)s[tot++]='0'+x%10,x/=10;
      }
    if(tot==0)s[tot++]='0';
    for (int i=0,j=tot-1;i<j;i++,j--)swap(s[i],s[j]);
    s[tot]=0;
    return tot;
  }
  int toarr(int *s)const{
    int tot=0;
    for (unsigned int i=0;i<a.size();i++)
      if(i+1==a.size()){
        int x=a[i];
        while(x)s[tot++]=x%10,x/=10;
      }else{
        int x=a[i];
        for (int j=0;j<4;j++)s[tot++]=x%10,x/=10;
      }
    if(tot==0)s[tot++]=0;
    return tot;
  }
  int comp(const Bignum&x)const{
    if(a.size()<x.a.size())return 1;
    if(a.size()>x.a.size())return -1;
    for (int i=a.size()-1;i>=0;i--)
      if(a[i]<x.a[i])return 1;
      else if(a[i]>x.a[i])return -1;
    return 0;
  }
  bool operator<(const Bignum&x)const{return comp(x)==1;}
  bool operator>(const Bignum&x)const{return comp(x)==-1;}
  bool operator<=(const Bignum&x)const{return comp(x)!=-1;}
  bool operator>=(const Bignum&x)const{return comp(x)!=1;}
  bool operator!=(const Bignum&x)const{return comp(x)!=0;}
  bool operator==(const Bignum&x)const{return comp(x)==0;}	
  Bignum& operator+=(const Bignum&x){
    int l=max(a.size(),x.a.size())+1;
    a.resize(l);
    for (unsigned int i=0;i<x.a.size();i++)a[i]+=x.a[i];
    for (int i=0;i<l;i++)if(a[i]>=10000)a[i]-=10000,a[i+1]++;
    clearzero();return *this;
  }
  Bignum& operator-=(const Bignum&x){
    for (unsigned int i=0;i<x.a.size();i++)a[i]-=x.a[i];
    for (unsigned int i=0;i<a.size();i++)if(a[i]<0)a[i]+=10000,a[i+1]--;
    clearzero();return *this;
  }
  Bignum operator+(const Bignum&x)const{Bignum y=*this;y+=x;return y;}		
  Bignum operator-(const Bignum&x)const{Bignum y=*this;y-=x;return y;}		
  Bignum operator*(const Bignum&x)const{
    int l=a.size()+x.a.size();
    Bignum z;z.a.clear();
    vector<long long>tmp;tmp.resize(l);
    for (unsigned int i=0;i<x.a.size();i++)
      for (unsigned int j=0;j<a.size();j++)
        tmp[i+j]+=x.a[i]*a[j];
    for (int i=0;i<l;i++){
      long long t=tmp[i]/10000;
      z.a.push_back(int(tmp[i]-t*10000));
      t?tmp[i+1]+=t:0;
    }
    z.clearzero();return z;
  }
  Bignum operator*(long long x)const{
    if(x>=10000)return *this * Bignum(x);
    int l=a.size()+2;
    Bignum z;z.a.resize(l);
    for (unsigned int i=0;i<a.size();i++)z.a[i]=a[i]*x;
    for (int i=0,t;i<l;i++)z.a[i+1]+=(t=z.a[i]/10000),z.a[i]-=t*10000;
    z.clearzero();return z;
  }
  friend Bignum operator*(long long x,const Bignum&a){return a*x;}
  Bignum& operator*=(long long x){return *this=*this*x;}
  Bignum& operator*=(const Bignum&x){return *this=*this*x;}		
  Bignum operator/(const Bignum &x)const{
    Bignum b=*this,q,tmp;q.a.resize(b.a.size());	
    for(int i=int(b.a.size())-int(x.a.size());b>=x;i--,b.clearzero()){
      tmp.a.assign(b.a.begin()+i,b.a.end());				
      int l=0,r=10000-1,m;
      while(l<=r){
        m=(l+r)>>1;
        if(x*m<=tmp)l=m+1;
        else r=m-1;
      }
      for (unsigned int j=0;j<tmp.a.size();j++)b.a[j+i]=0;
      q.a[i]=r;tmp-=x*r;
      for (unsigned int j=0;j<tmp.a.size();j++)b.a[j+i]=tmp.a[j];
    }
    q.clearzero();return q;
  }
  Bignum operator%(const Bignum &x)const{return *this-*this/x*x;}
  Bignum& operator/=(const Bignum &x){return *this=*this/x;}
  Bignum& operator%=(const Bignum &x){return *this=*this%x;}

  Bignum& operator/=(long long x){
    if(x>=10000)return *this/=Bignum(x);
    else{
      for (int i=int(a.size())-1;i>=0;i--){
        int t=a[i]/x;
        if(i)a[i-1]+=(a[i]-t*x)*10000;
        a[i]=t;
      }
      clearzero();
      return *this;
    }
  }
  Bignum operator/(long long x)const{
    if(x>=10000)return *this / Bignum(x);
    else{
      Bignum y=*this;y/=x;return y;
    }
  }
  long long operator%(long long x)const{
    if(x>(1ll<<40))return (*this%Bignum(x)).toint();
    else{
      long long ans=0;
      for (int i=int(a.size())-1;i>=0;i--)ans=(ans*10000+a[i])%x;
      return ans;
    }
  }
  int operator%(int x)const{
    return int(operator%((long long)x));
  }
  Bignum& operator%=(long long x){
    if(x>(1ll<<40))return *this%=Bignum(x);
    else return *this=*this%x;
  }
  int to2(int *s)const{
    int tot=0;
    vector<unsigned long long>t;
    for (unsigned int i=0;i<a.size();i++)t.push_back((unsigned long long)a[i]);
    while(!t.empty()){
      for (int i=int(t.size())-1;i>=0;i--){
        unsigned long long r=t[i]>>32;
        if(i==0){
          s[tot++]=int(t[i]&0xffffffff);
        }else{
          t[i-1]+=(t[i]&((unsigned long long)0xffffffff))*10000;
        }
        t[i]=r;
      }
      while(!t.empty() && t.back()==0)t.pop_back();
    }
    return tot;
  }
  bool input(){
    char c;vector<int> s;a.clear();
    while(((c=getchar())<'0' || c>'9') && c!=EOF);
    if(c==EOF){a.push_back(0);return 0;}
    s.push_back(c-'0');
    while((c=getchar())>='0'&&c<='9')s.push_back(c-'0');          
    int l=s.size();
    for (int i=l-1;i-3>=0;i-=4)a.push_back(s[i]+s[i-1]*10+s[i-2]*100+s[i-3]*1000);
    if(l&3){
      int tmp=0;
      for (int i=0;i<(l&3);i++)tmp=tmp*10+s[i];
      a.push_back(tmp);
    }
    clearzero();
    return 1;
  }
  void output()const{
    for (int i=int(a.size())-1;i>=0;i--)
      if(i==int(a.size())-1)printf("%d",a[i]);
      else printf("%04d",a[i]);
  }
  void outputln()const{
    output();putchar('\n');
  }
  friend Bignum max(const Bignum &a,const Bignum &b){return a>b?a:b;}
  friend Bignum min(const Bignum &a,const Bignum &b){return a<b?a:b;}
};

Bignum a, b;

int main(){
  a.input(); b.input();
  (a/b).outputln();
}

CompilationN/AN/ACompile OKScore: N/A

Testcase #195.695 ms148 KBAcceptedScore: 100


Judge Duck Online | 评测鸭在线
Server Time: 2024-10-05 12:14:17 | Loaded in 1 ms | Server Status
个人娱乐项目,仅供学习交流使用