Блог пользователя cartesian_bearrr

Автор cartesian_bearrr, история, 22 месяца назад, По-английски

Recently, I came upon this problem:

Given: A, C, and that ceil(A/B) < C

Find: the smallest B possible

My solution was using binary search. However, the official solution came up with this clever closed form formula:

B = ceil(A/(C-1))

I'm completely boggled by this equation. I've seen quite a few closed form equations involving floor and ceil before, but I can't find how they are derived.

Any help, explanation, or pointers appreciated!

Полный текст и комментарии »

  • Проголосовать: нравится
  • +14
  • Проголосовать: не нравится

Автор cartesian_bearrr, история, 2 года назад, По-английски

Recently, I saw a problem asking to output the fractional answer p/q as pq^−1 mod M, where p and q are relatively prime in the fraction and M was some prime modulus. My approach was to compute the numerator p and the denominator q separately, and then output p mod M * q^-1 mod M. However, how can I ensure that p and q is relatively prime with this approach? As p and q get gigantic, their factors are lost during the mod, and I can not ensure that p and q are relatively prime.

Thank for reading, and if the question is hard to understand I can clarify.

Полный текст и комментарии »

  • Проголосовать: нравится
  • +5
  • Проголосовать: не нравится