Here's the problem (IMO 2013 Problem 1): Assume that $k$ and $n$ are two positive integers. Prove that there exist positive integers $m_1 , \dots , m_k$ such that $1+\frac{2^k-1}{n}=\left(1+\frac1{m_1}\right)\cdots \left(1+\frac1{m_k}\right).$↵
↵
Think:↵
↵
<spoiler summary="Spoiler 0">↵
How is this related to segtrees?↵
</spoiler>↵
↵
↵
<spoiler summary="Spoiler 1">↵
Could you reformulate the "fraction multiplication" into something that is more similar to something related to segtrees?↵
</spoiler>↵
↵
↵
<spoiler summary="Spoiler 2">↵
Treat the fractions as ranges of denominator to numerator — of course, you may multiply a common number. Does it already look closer to something done with segtrees?Maybe relating the ranges of size 2^k to the fractions of the form 1 + 1/m↵
</spoiler>↵
↵
↵
↵
<spoiler summary="Spoiler 3">↵
Yes, each thing on the RHS may be taken as ranges. But you need the range length (including start, but not end) to be a divisor of the numerator. Hmmm now how could we do this? ↵
</spoiler>↵
↵
↵
<spoiler summary="Spoiler 4">↵
Let's try to make all range lengths powers of two (note: for example, the range length of [4,8] is 8-4=4). In a segment tree that covers the range (1,1024), look at all the nodes that cover ranges of size 8. Do they have anything in common with fractions of the form 1+1/m?↵
</spoiler>↵
↵
<spoiler summary="Mega Spoiler">↵
What happens when you do a range sum query? What happens to the lengths?↵
</spoiler>↵
↵
Here's a generalization, which is much easier once you've found the segtree solution to the above problem. Assume that $k$ and $n$ are two positive integers. Prove that there exist positive integers $m_1 , \dots , m_k$ such that $1+\frac{k}{n}=\left(1+\frac1{m_1}\right)\cdots \left(1+\frac1{m_l}\right)$, where $l$ is an integer and $l \leq 2 \times ceil(log_2(k/2+1))$. ↵
↵
Challenge: Implement the two variants of the problem. In the generalization, you are given $k$ and $n$, and you are required to output an array that consists of $m_1$, $m_2$, ..., $m_l$.
↵
Think:↵
↵
<spoiler summary="Spoiler 0">↵
How is this related to segtrees?↵
</spoiler>↵
↵
↵
<spoiler summary="Spoiler 1">↵
Could you reformulate the "fraction multiplication" into something that is more similar to something related to segtrees?↵
</spoiler>↵
↵
↵
<spoiler summary="Spoiler 2">↵
</spoiler>↵
↵
↵
↵
<spoiler summary="Spoiler 3">↵
Yes, each thing on the RHS may be taken as ranges. But you need the range length (including start, but not end) to be a divisor of the numerator. Hmmm now how could we do this? ↵
</spoiler>↵
↵
↵
<spoiler summary="Spoiler 4">↵
</spoiler>↵
↵
<spoiler summary="Mega Spoiler">↵
What happens when you do a range sum query? What happens to the lengths?↵
</spoiler>↵
↵
Here's a generalization, which is much easier once you've found the segtree solution to the above problem. Assume that $k$ and $n$ are two positive integers. Prove that there exist positive integers $m_1 , \dots , m_k$ such that $1+\frac{k}{n}=\left(1+\frac1{m_1}\right)\cdots \left(1+\frac1{m_l}\right)$, where $l$ is an integer and $l \leq 2 \times ceil(log_2(k/2+1))$. ↵
↵
Challenge: Implement the two variants of the problem. In the generalization, you are given $k$ and $n$, and you are required to output an array that consists of $m_1$, $m_2$, ..., $m_l$.
