National Olympiad in Informatics, China, 2001
Day 2, Problem 1 - Applications of Arctangent
The inverse tangent function can be expressed as an infinite series, as shown below:
It is commonly known that the inverse tangent function can be used to compute π. For example, an easy way to compute π is using the method:
Of course, this method is rather inefficient. We can apply the tangent angle sum identity:
After some simple manipulation, the follow is obtained:
Using this identity, let and , then . Therefore:
Using the inverse tangents of and to calculate , the speed is drastically improved.
We take equation (4) and write it in the following form:
where a, b, and c are each positive integers.
The problem is, for a given a (1 ≤ a ≤ 60000), 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.
The input consists of a single positive integer a, where 1 ≤ a ≤ 60000.
The output should contain a single integer, the value of b + c.
Point Value: 15
Time Limit: 0.25s
Memory Limit: 64M
Added: May 08, 2014
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3