反正切函数可展开成无穷级数，有如下公式
　　　　　　　　　　　　　　　　　　公式(1)
　　使用反正切函数计算是一种常用的方法。例如，最简单的计算的方法：
　　　　　　　　　　　　　　　　　　　　　 公式(2)
　　然而，这种方法的效率很低，但我们可以根据角度和的正切函数公式：
　　　　　　　　　　　　　　　　　　　　　 　公式(3)
　　通过简单的变换得到：
　　　　　　　　　　　　　　　　　　　　公式(4)
　　利用这个公式，令 ，有
　　　　　　　　　　
　　使用的反正切来计算，速度就快多了。
　　我们将公式(4)写成如下形式
　　　　　　　　　　
　　其中a 、b 和c 均为正整数。
　　我们的问题是：对于每一个给定的a（ ），求b＋c的值。我们保证对于任意的a都存在整数解。如果有多个解，要求你给出b+c最小的解。

输入文件（arctan.in）
　　输入文件中只有一个正整数a，其中 。

输出文件（arctan.out）
　　输出文件中只有一个整数，为b+c的值。

输入样例
1

输出样例
5

Noi2001之反正切函数的应用（Arctan）解题报告

福州第一中学 陈阳

【题目大意】
　　题目给出了两个公式：和 ，要求我们在知道a的情况下求出b+c的最小值，并且a、b、c都是正整数。

【算法分析】
　　看到这个题目，我们往往会考虑是否可以通过某种数学方法算出答案。但是我们都对arctan的性质了解不够，因此我们先试考虑a、b、c之间的代数关系。我们现根据题目给出的公式做以下一些计算：
　　　　　 ，
　　　　　
　　　　

　　根据以上的推导，由于a、b、c都是正整数，a是定值，我们就得到一种算法：枚举b的值，如果在当前b的取值下，算出的c值是正整数的话，那么现在的b+c就是一个可行值。我们从a+1开始枚举b（如果b<a，那么c<0），直到b=当前求得的最小值为止。这种算法简单，但是耗时太大，往往再得到最优解以后，不能及时停止算法（因为根据下面的分析大致可知，b+c的值可以接近b2，所以在枚举到最优解的b之后，还要算大约b2次才能停止算法），而且取整运算有精度问题，算ab的时候也很容易超界，所以这不是一种有效的算法。

　　我们根据上面关于c的公式，把两边都加上b，就得到：
　　

　　如果按照这个公式去枚举b，虽然可以直接算出b+c的值，但是算比算ab更容易超界（因为b>a），这也没有解决怎么停止算法的问题，所以也不行。但是，从这个公式我们发现，所求的b+c，实际上可以表示成一个关于b的函数，设（b是正整数），那么这个函数由什么性质呢？我们利用求最值的方法作以下计算：
　　
　　（当时取等号）
　　（以上b>a,当a足够大的时候，这个值）

　　 这样是得到了b>a时b+c的最小值，但是这个最小值是在b为实数的条件下得到的，并不能作为本题的解。不过通过这个最小值，我们可以猜测，在b>a时函数很可能由一个单调递减区间和一个单调递增区间，而当b、c为整数的时候，这个点的函数值一定是最靠近函数的最小值。我们来看下面一幅图：
　　　　　

　　这幅图是当a=10时函数的部分近似图像。我们看到，在b<=a的时候，函数对我们解题是没有意义的。而在b>a时，函数先是单调递减，然后开始缓慢单调递增（当然，通过数学分析也可以得到这个结论）。因此，这也就是说，函数值由一个最小值，当我们没有找到最小值的时候，扩大b的值，b+c的值会减小，而如果找到最小值了，那么b+c的值会扩大，这也就说明了最小值已经找到，算法可以停止。这样，我们的算法就是我们记录遍历b的过程中每一个可取（也就是说b+c为整数时）的b+c的值，如果当前可取的b+c的值比上一个可取值大，那么程序就可以结束，上一个可取的b+c的值就是我们要的解。这样所遍历b的值就很少，大约是a。实际上我们再仔细观察图像，就会知道：若b为实数，时有最小值。而又略大于2a。因此，当时，整数b离取最小值的实数b最接近，再根据图像。发现到达最小值以后，函数值增长缓慢，因此可以认为b=2*a+1就是本题的搜索上限。而搜索下限从a+1开始，这样搜索个数大约为a。既复杂度为O(a)，是可以接受俄。

【解题总结】
　　当时我和同学参加同步赛，用搜索法，开了数台机器跑了几个小时，大约跑出了一半的数据（其中还有一部分是错误的）记录在程序里面。如果一看到这样的题目，发现没有简便的方法，就用搜索等方法解决，倒不如认真的分析题目，往往会得到事半功倍的便捷方法。