NOI '01 P4 - Applications of Arctangent

View as PDF

Submit solution

Points: 15
Time limit: 0.18s
Memory limit: 64M

Problem type
National Olympiad in Informatics, China, 2001

The inverse tangent function can be expressed as an infinite series, as shown below:

\displaystyle \begin{align}
\arctan(x) = \sum_{n=0}^\infty \frac{(-1)^n x^{2n+1}}{2n+1} \quad (0 \le x \le 1)
\end{align} \tag{1}

It is commonly known that the inverse tangent function can be used to compute \pi. For example, an easy way to compute \pi is using the method:

\displaystyle \begin{align}
\pi &= 4\arctan(1) \\
&= 4 \left(1-\frac 1 3+\frac 1 5-\frac 1 7+\frac 1 9-\frac 1 {11}+\dots\right)
\end{align} \tag{2}

Of course, this method is rather inefficient. We can apply the tangent angle sum identity:

\displaystyle \begin{align}
\tan(\alpha+\beta) = \frac{\tan(\alpha)+\tan(\beta)}{1-\tan(\alpha)\tan(\beta)}
\end{align} \tag{3}

After some simple manipulation, the following is obtained:

\displaystyle \begin{align}
\arctan(p) + \arctan(q) = \arctan\left(\frac{p+q}{1-pq}\right)
\end{align} \tag{4}

Using this identity, let p=\dfrac{1}{2} and q=\dfrac{1}{3}, then \dfrac{p+q}{1-pq}=1. Therefore:

\displaystyle \arctan\left(\frac 1 2\right)+\arctan\left(\frac 1 3\right) = \arctan\left(\frac{\frac 1 2+\frac 1 3}{1-\frac 1 2 \cdot \frac 1 3}\right) = \arctan(1)

Using the inverse tangents of \dfrac 1 2 and \dfrac 1 3 to calculate \arctan(1), the speed is drastically improved.

We take equation (4) and write it in the following form:

\displaystyle \arctan\left(\frac 1 a\right) = \arctan\left(\frac 1 b\right)+\arctan\left(\frac 1 c\right)

where a, b, and c are each positive integers.

The problem is, for a given a (1 \le a \le 60\,000), find the value of b + c. It is guaranteed that for any a there will always exist an integer solution. If there are multiple solutions, you are required to find the minimum value of b + c.

Input Specification

The input consists of a single positive integer a, where 1 \le a \le 60\,000.

Output Specification

The output should contain a single integer, the value of b + c.

Sample Input

1

Sample Output

5

Problem translated to English by Alex.


Comments

There are no comments at the moment.