题目地址：POJ：1183 — 反正切函数的应用

题目描述

反正切函数可展开成无穷级数，有如下公式
\arctan x = \sum_{n=0}^\infty \frac{(-1)^n x^{2n+1}}{2n+1} \ (0 \leq x \leq 1) \ (1)
使用反正切函数计算\pi是一种常用的方法。例如，最简单的计算\pi的方法：
\begin{aligned} \pi & = 4 \arctan 1 \\ & = 4(1 - \frac{1}{3} + \frac{1}{5} - \frac{1}{7} + \frac{1}{9} - \frac{1}{11} + \cdots) \ (2) \end{aligned}
然而，这种方法的效率很低，但我们可以根据角度和的正切函数公式：
\tan(\alpha + \beta) = \frac{\tan \alpha + \tan \beta}{1 - \tan \alpha \tan \beta} \ (3)
通过简单的变换得到：
\arctan p + \arctan q = \arctan(\frac{p+q}{1-pq}) \ (4)
利用这个公式，令p=\frac{1}{2}, q=\frac{1}{3}，则\frac{p+q}{1-pq} = 1，有
\arctan \frac{1}{2} + \arctan \frac{1}{3} = \arctan(\frac{\frac{1}{2} + \frac{1}{3}}{1 - \frac{1}{2} \times \frac{1}{3}}) = \arctan 1
使用\frac{1}{2}和\frac{1}{3}的反正切来计算\arctan 1，速度就快多了。
我们将公式(4)写成如下形式
\arctan \frac{1}{a} = \arctan \frac{1}{b} + \arctan \frac{1}{c}
其中a、b和c均为正整数。
我们的问题是：对于每一个给定的a（1≤a≤60000），求b+c的值。我们保证对于任意的a都存在整数解。如果有多个解，要求你给出b+c最小的解。

输入输出格式

输入格式：
输入文件中只有一个正整数a，其中1≤a≤60000。

输出格式：
输出文件中只有一个整数，为b+c的值。

输入输出样例

输入样例#1：

1

输出样例#1：

5

题解

本题为推式子题，内容不会超过高中知识范畴，请各位放心食用。
首先我们将给定式进行公式(4)的变换，得到的式子如下
\arctan \frac{1}{a} = \arctan(\frac{\frac{1}{b} + \frac{1}{c}}{1 - \frac{1}{bc}})
进而因为反正切函数的性质，可以直接得到
\frac{1}{a} = \frac{\frac{1}{b} + \frac{1}{c}}{1 - \frac{1}{bc}}
进行化简后可以得到
a = \frac{bc-1}{b+c}
b和c都在式子里不好处理，我们考虑用S=b+c把其中一个消掉，然后把S表示成另一个的函数，函数写出来如下
S(c) = c + a + \frac{a^2+1}{c-a}
现在我们对这个函数在正整数范围内求最小值，如果不考虑整数，我们可以利用均值不等式知道最小值应该在c = a + \sqrt{a^2 + 1}处取到，但是此时函数值可能不是一个整数，不满足b、c都是正整数的条件。因此我们可以考虑在这个值附近枚举c。因为这是一个双曲线，最小整点在临界点两边取得都有可能，那我们就在两边枚举就好了。
其实你还可以接着分析，因为c越靠近a，函数值增长得越快，越远离a，函数值增长的越慢，一般来说应该在向左枚举的过程中最先找到整点吧。但是这个还没办法证明。

代码

// Code by KSkun, 2018/3
#include <cstdio>
#include <cmath>

typedef long long LL;

LL a;

inline LL cals(LL c) {
    return c + a + (a * a + 1) / (c - a);
}

int main() {
    scanf("%lld", &a);
    LL c = a + sqrt(a * a + 1), c1 = c, c2 = c;
    for(;; c1--, c2++) {
        if((c1 - a) && (a * a + 1) % (c1 - a) == 0) {
            printf("%lld", cals(c1));
            break;
        }
        if((c2 - a) && (a * a + 1) % (c2 - a) == 0) {
            printf("%lld", cals(c2));
            break;
        }
    }
    return 0;
}