#P1183. 反正切函数的应用

反正切函数的应用

问题描述

反正切函数可以展开成无穷级数,有如下公式:

$$\arctan(x) = \sum_{k=0}^{\infty} \frac{(-1)^k}{2k+1} x^{2k+1} \quad \text{(其中 $0 \leq x \leq 1$)} \quad \text{公式 (1)} $$

使用反正切函数计算 π\pi 是一种常用的方法。例如,最简单的计算 π\pi 的方法是:

$$\pi = 4 \arctan(1) = 4 \left(1 - \frac{1}{3} + \frac{1}{5} - \frac{1}{7} + \frac{1}{9} - \frac{1}{11} + \cdots \right) \quad \text{公式 (2)} $$

然而,这种方法的效率很低。我们可以根据角度和的正切函数公式:

$$\tan(a + b) = \frac{\tan(a) + \tan(b)}{1 - \tan(a) \tan(b)} \quad \text{公式 (3)} $$

通过简单的变换得到:

$$\arctan(p) + \arctan(q) = \arctan\left(\frac{p + q}{1 - p q}\right) \quad \text{公式 (4)} $$

利用这个公式,令 p=12p = \frac{1}{2}q=13q = \frac{1}{3},则 p+q1pq=1\frac{p + q}{1 - p q} = 1,因此有:

$$\arctan\left(\frac{1}{2}\right) + \arctan\left(\frac{1}{3}\right) = \arctan(1) $$

使用 12\frac{1}{2}13\frac{1}{3} 的反正切来计算 arctan(1)\arctan(1),速度会快很多。

我们将公式 (4) 写成如下形式:

$$\arctan\left(\frac{1}{a}\right) = \arctan\left(\frac{1}{b}\right) + \arctan\left(\frac{1}{c}\right) $$

其中 aabbcc 均为正整数。

我们的问题是:对于每一个给定的 aa1a600001 \leq a \leq 60000),求 b+cb + c 的值。我们保证对于任意的 aa 都存在整数解。如果有多个解,要求给出 b+cb + c 最小的解。

输入格式

输入文件中只有一个正整数 aa,其中 1a600001 \leq a \leq 60000

输出格式

输出文件中只有一个整数,为 b+cb + c 的值。

示例输入

1

示例输出

5

题目来源

NOI 2001