What are some efficient ways to divide 'a' by 'b' where the range is :

-10^300 <= a,b <= +10^300

# | User | Rating |
---|---|---|

1 | tourist | 3870 |

2 | Benq | 3618 |

3 | Miracle03 | 3453 |

4 | peehs_moorhsum | 3430 |

5 | Radewoosh | 3418 |

6 | Petr | 3408 |

7 | maroonrk | 3387 |

8 | sunset | 3338 |

9 | ko_osaga | 3334 |

9 | jiangly | 3334 |

# | User | Contrib. |
---|---|---|

1 | YouKn0wWho | 214 |

2 | 1-gon | 203 |

3 | Um_nik | 195 |

4 | Errichto | 181 |

5 | awoo | 180 |

6 | sus | 176 |

6 | tourist | 176 |

8 | antontrygubO_o | 173 |

9 | maroonrk | 170 |

10 | -is-this-fft- | 169 |

What are some efficient ways to divide 'a' by 'b' where the range is :

-10^300 <= a,b <= +10^300

↑

↓

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/06/2021 12:29:53 (i1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

Since the answer of

`a/b`

is between 0 and a, we could use binary_search. Complexity:`log(a)`

, which is around 1000.That's actually since in every iteration of binary search you need to multiply two numbers.

Fortunately there's an easier and faster way in

O(n^{2}) (hereafternis the number of digits), assuming the numeric basedis a small constant (typically 2, 10, or 16).Start with

x= 0, then, for eachifromndown to 0, keep incrementingxbyd^{i}as long asxb≤a. This "increment and compare" operation can be done inO(n) by performing it not onx, but on the productxb— you can addbd^{i}to any number by simply appendingizeroes to thed-ary representation ofband performing addition as usual. Running time of this algorithm isO(d·n^{2}). For large values ofdyou can use binary search inside each iteration of the outer loop, instead of a simple loop which keeps addingd^{i}, so the complexity becomes .There is a way to do it in , where

Nis the sum of lengths of the numbers. Link. But it's masochistic to implement it (as far as I remember).