Logo CloudLunar

“CodeVS/3118”的版本间的差异

（以“分类:高精度 ==摘要== {{信息题|高精度练习之除法|http://www.codevs.cn/problem/3118/|1|100|错误的去高位|80|time=2015-2-3 23:45:10}} ==题意...”为内容创建页面）
 
小 （→‎题解： 补充另一种做法）
 
第6行： 第6行：
 
==题解==
 
==题解==
 
*以前做过一题高精度除法，但是保证答案为lld以内，所以可以直接二分。这一题也可以二分做，不同在于除以2没有定义，但是很容易想到按位除以2，处理一下即可。
 
*以前做过一题高精度除法，但是保证答案为lld以内，所以可以直接二分。这一题也可以二分做，不同在于除以2没有定义，但是很容易想到按位除以2，处理一下即可。
−
*于是四则运算凑齐了^_^不过这里的除法不涉及负数（一步一步的给库加内容的过程可以参照 [[CodeVS/3118|CodeVS/3118高精度加法]]、[[CodeVS/3117|CodeVS/3117高精度乘法]]、[[CodeVS/3115|CodeVS/3115高精度减法]]）。
+
*于是四则运算凑齐了^_^不过这里的除法不涉及负数（一步一步的给库加内容的过程可以参照 [[CodeVS/3116|CodeVS/3116高精度加法]]、[[CodeVS/3117|CodeVS/3117高精度乘法]]、[[CodeVS/3115|CodeVS/3115高精度减法]]）。
 +
*这种做法是除法转化为乘法来做，似乎也有乘法转换为减法的做法，请参见：http://codevs.cn/wiki/solution/?problem_id=3118
 +
 
 
==代码==
 
==代码==
 
{{折叠|3118.cpp代码已折叠
 
{{折叠|3118.cpp代码已折叠

2015年2月3日 (二) 23:50的最后版本

摘要

题目链接 难度等级 完成状态 完成分数 最后编辑时间 失误原因（初次提交分数）
高精度练习之除法 ★☆☆☆☆ 答案正确 100 2015-2-3 23:45:10 错误的去高位（80）

题意

500位以内的除法。

题解

代码

3118.cpp代码已折叠
展开折叠内容
显示/移除行号
  1. #include<iostream>
  2. #include<iomanip>
  3. #include<algorithm>
  4. #include<vector>
  5. using namespace std;
  6. class largeInt
  7. {
  8.     public:
  9.         const int size() const
  10.         {
  11.             return u.size();
  12.         }
  13.         largeInt()
  14.         {
  15.             u.clear();
  16.             u.push_back(0);
  17.         }
  18.         largeInt(const int &number)
  19.         {
  20.             u.clear();
  21.             u.push_back(number);
  22.             carry();
  23.         }
  24.         friend istream& operator >> (istream& os,largeInt &ob)
  25.         {
  26.             ob.u.clear();
  27.             string original;
  28.             os>>original;
  29.             for(int i=original.size()-1,j=0,p=1;i>=0;--i)
  30.             {
  31.                 j+=(original[i]-'0')*p;
  32.                 p*=10;
  33.                 if((!i) || p==10000)
  34.                 {
  35.                     ob.u.push_back(j);
  36.                     j=0;
  37.                     p=1;
  38.                 }
  39.             }
  40.             return os;
  41.         }
  42.         friend ostream& operator << (ostream& os,const largeInt &ob)
  43.         {
  44.             os<<setw(0)<<setfill('0')<<ob.u[ob.size()-1];
  45.             for(int i=ob.size()-2;i>=0;--i)
  46.                 os<<setw(4)<<setfill('0')<<ob.u[i];
  47.             return os;
  48.         }
  49.         friend const bool operator <(const largeInt &a,const largeInt &b)
  50.         {
  51.             if(a.size()==b.size())
  52.             {
  53.                 for(int i=a.size()-1;i>=0;--i){
  54.                     if(a.u[i]!=b.u[i])
  55.                         return a.u[i]<b.u[i];
  56.                 }
  57.                 return 0;
  58.             }
  59.             return a.size()<b.size();
  60.         }
  61.         friend const largeInt operator +(const largeInt &a,const largeInt &b)
  62.         {
  63.             largeInt r;
  64.             r.u.resize(max(a.size(),b.size()));
  65.             for(int i=0;i<r.size();++i)
  66.             {
  67.                 if(i<a.size())
  68.                     r.u[i]+=a.u[i];
  69.                 if(i<b.size())
  70.                     r.u[i]+=b.u[i];
  71.             }
  72.             r.carry();
  73.             return r;
  74.         }
  75.         friend const largeInt operator *(const largeInt &a,const largeInt &b)
  76.         {
  77.             largeInt r;
  78.             r.u.resize(a.size()+b.size());
  79.             for(int i=0;i<a.size();++i)
  80.             {
  81.                 for(int j=0;j<b.size();++j)
  82.                 {
  83.                     r.u[i+j]+=a.u[i]*b.u[j];
  84.                 }
  85.             }
  86.             r.carry();
  87.             return r;
  88.         }
  89.         friend const largeInt operator /(const largeInt &a,const largeInt &b)
  90.         {
  91.            largeInt left=0,right=a,mid;
  92.            while(left+1<right)
  93.            {
  94.                 mid=div(left+right);
  95.                 if(a<mid*b)
  96.                     right=mid;
  97.                 else
  98.                     left=mid;
  99.            }
  100.            return left;
  101.         }
  102.         friend largeInt div(largeInt a)
  103.         {
  104.             for(int i=a.size()-1;i>=0;--i)
  105.             {
  106.                 if(a.u[i]%2&&i>=1)
  107.                 {
  108.                     a.u[i-1]+=10000;
  109.                 }
  110.                 a.u[i]/=2;
  111.                // cout<<"{"<<a.u[i]<<"}";
  112.             }
  113.             a.carry();
  114.             return a;
  115.         }
  116.     private:
  117.         vector<int> u;
  118.         void carry()
  119.         {
  120.             for(int i=0;i<size();++i)
  121.             {
  122.                 if(u[i]>=10000)
  123.                 {
  124.                     if(i==size()-1)
  125.                         u.push_back(u[i]/10000);
  126.                     else
  127.                         u[i+1]+=u[i]/10000;
  128.                     u[i]%=10000;
  129.                 }
  130.             }
  131.             for(int i=size()-1;i!=0;--i)
  132.             {
  133.                 if(u[i]==0)
  134.                 {
  135.                     u.pop_back();
  136.                 }else{
  137.                     break;//fixed//
  138.                 }
  139.             }
  140.         }
  141. };
  142. int main()
  143. {
  144.     largeInt a,b;
  145.     cin>>a>>b;
  146.     cout<<a/b;
  147. }
取自“https://blog.CloudLunar.com/index.php?title=CodeVS/3118&oldid=1032”
分享ShareQQ空间新浪微博人人网一键分享TwitterFacebook

著作权声明[编辑]

关于[编辑]