bhikkhu's blog

By bhikkhu, history, 8 years ago, In English

http://codeforces.net/contest/758/problem/F

Guys can anybody explain why the upper bounds for x and y for the ratio d = x/y is n-1 th root of 'r'?

I know it myself but I want to know what other coders think about it.

So basically explain why x <= power(r, 1 / (n — 1)) and y <= power(r, 1 / (n — 1))?

  • Vote: I like it
  • -6
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by bhikkhu (previous revision, new revision, compare).

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Assuming you're talking about the variables x and y defined in the editorial, for y we have:

b × yn - 1 ≤ r

The case for x is the same if you just replace y with x.