Maths Olympiad Prep

Library / /294 of 520

Number theory Difficulty 6.2 National olympiad Prove it

Theorem 1.7. There is an algorithm to find the quotient q=[a/b]q=[a / b], when the 2n2 n-bit integer aa is divided by the integer bb having no more than nn bits, using O(M(n))O(M(n)) bit operations, where M(n)M(n) is the number of bit operations needed to multiply two nn-bit integers.

Solution

None

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.