自动搬运

查看原文

来自洛谷，原作者为

	registerGen 一切都是野蛮的。要反对这种野蛮，我们必须也学会野蛮。

搬运于2025-08-24 22:13:31，当前版本为作者最后更新于2019-12-02 22:41:49，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

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}$

$$\begin{aligned} \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)$

2. 下面我们来看 $(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;
}