CodeVS3118高精度练习之除法
4998+
作者:crxis 发布:2017-06-18 分类:高精度
题目大意:给出两个正整数A和B,计算A/B整数部分的值。保证A和B的位数不超过500位。(本文介绍高精度除以高精度的2种不同方法)
输入描述 Input Description
读入两个用空格隔开的正整数
输出描述 Output Description
输出A/B整数部分的值
样例输入 Sample Input
15 4
样例输出 Sample Output
3
数据范围及提示 Data Size & Hint
两个正整数的位数不超过500位
解题思路
1、模拟除法运算,一位一位把商求出来,需要注意截取部分被除数、逐位试商、对齐相减……很多麻烦事,总体复杂度9*250^2
2、结果最多500位,在2^2000以内,可以二分答案(不超过2000次),每次把猜的答案c与除数b相乘(乘法复杂度250^2),并将乘积跟被除数a比较。
程序实现
1、逐位求商:代码短,纯模拟,复杂度低,但第一次写可能不太舒服(函数中数组用memset注意不要错取指针的size)
2、二分答案:虽然代码多,复杂度稍高,但是好理解,写起来比较舒服