题解 P5695 【[NOI2001]反正切函数的应用】

· · 题解

Upd on 2020/02/17：改了下 \LaTeX 并写了时间复杂度更低的 Code

P5695题面

这道题是道数学题，但代码十分简单。

良心出题人已经把公式扔给我们了：

\operatorname{arctan}(p)+\operatorname{arctan}(q)=\operatorname{arctan}\left(\dfrac{p+q}{1-pq}\right)\qquad(1)

于是，我们在 (1) 中令 p=\dfrac{1}{b},\ q=\dfrac{1}{c} ，则：

\operatorname{arctan}\left(\dfrac{1}{a}\right)=\operatorname{arctan}\left(\dfrac{1}{b}\right)+\operatorname{arctan}\left(\dfrac{1}{c}\right)=\operatorname{arctan}\left(\dfrac{b+c}{bc-1}\right) \therefore \dfrac{1}{a}=\dfrac{b+c}{bc-1}

于是 c=\dfrac{ab+1}{b-a}

\therefore b+c&=b+\dfrac{ab+1}{b-a}\\ &=\dfrac{b^{2}+1}{b-a}\\ &=\frac{b^{2}-a^{2}+a^{2}+1}{b-a}\\ &=b+a+\frac{a^{2}+1}{b-a}\qquad(2)\\ &=\big(b-a\big)+\frac{a^{2}+1}{b-a}+2a\qquad(3) \end{aligned}
  1. 由 (2) 知 c=a+\dfrac{a^{2}+1}{b-a}

因为 c 是正整数，所以 b>a 且 (b-a)\left|\right.(a^{2}+1)

  1. 下面我们来看 (3) 式，这是典型的对勾函数，当 b-a 和 \dfrac{a^{2}+1}{b-a} 最接近时，(3) 式有最小值。

综上，我们得到：b-a 取最接近 \sqrt{a^{2}+1} 且比它大且为 a^{2}+1 的约数时，b+c 最小。

代码：（时间复杂度 O(a)）

#include<cstdio>

#define int long long // 三年 OI 一场空，不开 long long 见祖宗

signed main()
{
    int a;
    scanf("%lld",&a);
    int b,c;
    int s=a*a+1;
    for(int i=a;i>=1;i--)
        if(s%i==0)
        {
            b=i+s/a;
            break;
        }
    c=(a*b+1)/(b-a);
    printf("%lld\n",b+c);
    return 0;
}