高精度除法

大雪菜的課（筆記）

基礎算法（二）

1.高精度

(1).高精度除法

模闆(高精度除以低精度 —— 模闆題 AcWing 794. 高精度除法)

vector<int> div(vector<int> &a,int b,int& r){
	vector<int> c;
	r=0;
	for(int i=a.size()-1;i>=0;i--){
		r=r*10+a[i];
		c.push_back(r/b);
		r%=b;
	}
	reverse(c.begin(),c.end());
	while(c.size()>1&&c.back()==0)	c.pop_back();
	return c;
 }
           

AcWing794. 高精度除法

給定兩個非負整數A，B，請你計算 A / B的商和餘數。

輸入格式

共兩行，第一行包含整數A，第二行包含整數B。

輸出格式

共兩行，第一行輸出所求的商，第二行輸出所求餘數。

資料範圍

1≤A的長度≤100000,

1≤B≤10000

B 一定不為0

輸入樣例：

7

2

輸出樣例：

3

1

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
vector<int> div(vector<int> a,int b,int &r){
	vector<int> c;
	for(int i=a.size()-1;i>=0;i--){
		r=r*10+a[i];
		c.push_back(r/b);
		r%=b;
	}
	reverse(c.begin(),c.end());
	while(c.size()>1&&c.back()==0)	c.pop_back();
	return c;
}
int main()
{
	string s;
	int b,r=0;
	cin>>s>>b;
	vector<int> a;
	for(int i=s.size()-1;i>=0;i--)
		a.push_back(s[i]-'0');
	auto c=div(a,b,r);
	for(int i=c.size()-1;i>=0;i--)
		cout<<c[i];
	printf("\n%d",r);
	return 0;
}