(以“分类:高精度 ==摘要== {{信息题|高精度练习之除法|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代码已折叠
展开折叠内容
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<vector>
using namespace std;
class largeInt
{
    public:
        const int size() const
        {
            return u.size();
        }
        largeInt()
        {
            u.clear();
            u.push_back(0);
        }
        largeInt(const int &number)
        {
            u.clear();
            u.push_back(number);
            carry();
        }
        friend istream& operator >> (istream& os,largeInt &ob)
        {
            ob.u.clear();
            string original;
            os>>original;
            for(int i=original.size()-1,j=0,p=1;i>=0;--i)
            {
                j+=(original[i]-'0')*p;
                p*=10;
                if((!i) || p==10000)
                {
                    ob.u.push_back(j);
                    j=0;
                    p=1;
                }
            }
            return os;
        }
        friend ostream& operator << (ostream& os,const largeInt &ob)
        {
            os<<setw(0)<<setfill('0')<<ob.u[ob.size()-1];
            for(int i=ob.size()-2;i>=0;--i)
                os<<setw(4)<<setfill('0')<<ob.u[i];
            return os;
        }
        friend const bool operator <(const largeInt &a,const largeInt &b)
        {
            if(a.size()==b.size())
            {
                for(int i=a.size()-1;i>=0;--i){
                    if(a.u[i]!=b.u[i])
                        return a.u[i]<b.u[i];
                }
                return 0;
            }
            return a.size()<b.size();
        }
        friend const largeInt operator +(const largeInt &a,const largeInt &b)
        {
            largeInt r;
            r.u.resize(max(a.size(),b.size()));
            for(int i=0;i<r.size();++i)
            {
                if(i<a.size())
                    r.u[i]+=a.u[i];
                if(i<b.size())
                    r.u[i]+=b.u[i];
            }
            r.carry();
            return r;
        }
        friend const largeInt operator *(const largeInt &a,const largeInt &b)
        {
            largeInt r;
            r.u.resize(a.size()+b.size());
            for(int i=0;i<a.size();++i)
            {
                for(int j=0;j<b.size();++j)
                {
                    r.u[i+j]+=a.u[i]*b.u[j];
                }
            }
            r.carry();
            return r;
        }
        friend const largeInt operator /(const largeInt &a,const largeInt &b)
        {
           largeInt left=0,right=a,mid;
           while(left+1<right)
           {
                mid=div(left+right);
                if(a<mid*b)
                    right=mid;
                else
                    left=mid;
           }
           return left;
        }
        friend largeInt div(largeInt a)
        {
            for(int i=a.size()-1;i>=0;--i)
            {
                if(a.u[i]%2&&i>=1)
                {
                    a.u[i-1]+=10000;
                }
                a.u[i]/=2;
               // cout<<"{"<<a.u[i]<<"}";
            }
            a.carry();
            return a;
        }
    private:
        vector<int> u;
        void carry()
        {
            for(int i=0;i<size();++i)
            {
                if(u[i]>=10000)
                {
                    if(i==size()-1)
                        u.push_back(u[i]/10000);
                    else
                        u[i+1]+=u[i]/10000;
                    u[i]%=10000;
                }
            }
            for(int i=size()-1;i!=0;--i)
            {
                if(u[i]==0)
                {
                    u.pop_back();
                }else{
                    break;//fixed//
                }
            }
        }
};
int main()
{
    largeInt a,b;
    cin>>a>>b;
    cout<<a/b;
}

著作权声明[编辑]

关于[编辑]