Power OJ 2402: Arctan

朴灿烈づ我的快乐病毒、 2021-09-28 04:44 203阅读 0赞

# [Power OJ 2402: Arctan][Power OJ 2402_ Arctan] #

## Description ##

> 话说上个星期四晚上大家呆在实验室，寅队爆料网上一则冷笑话：男的叫郑璇，女的叫余璇，请问结婚后他们的孩子叫什么？我们现在不管他们的孩子叫郑切还是余切。Kevin只知道自己看过一个如下公式：arctan(1/A)=arctan(1/B)+arctan(1/C)，例如当A=1,B=2,C=3时上述等式成立。  
> 现在给定A，我们要求出最小的sum=B+C,使得A,B,C满足上述等式。

## Input ##

> 输入数据有多组，每组输入一个A(1<=A<=1000000).

## Output ##

> 输出满足上述等式的最小sum值,(sum=B+C)。

首先我们来分析一下，根据反正切相加（减）定理  
![在这里插入图片描述][20190213193502926.png]  
得到A,B,C之间存在如下关系：  
B*C-A*B-A*C=1  
=>(B-A)C=1+AB  
=>C=(1+A*B)/(B-A)  
=>C=(1+A(B-A+A))/(B-A)=(A²+1)/(B-A)+A  
=>B+C=B+(A²+1)/(B-A)+A  
=>B+C=B-A+2*A+(A²+1)/(B-A)  
不妨设t=B-A;  
B+C=t+2*A+(A²+1)/t；  
欲求最小sum值，即求t+2*A+(A²+1)/t的最小值  
又因为t，sum均为整数，所以进行枚举  
枚举A²+1的所有不大于sqrt（A²+1）的所有约数，找到最大的约数即可  
如果不放心的话可以做比较更新最小t+2*A+(A²+1)/t，因为该函数的(A²+1)/t的影响远大于t本身，所以博主只选择了最大的约数进行考虑。  
样例代码如下：

#include <bits/stdc++.h> 
    using namespace std;
    int main()
    { 
        long long a,i;
        while(scanf("%lld", &a)!=EOF)
        { 
        	for(i=sqrt(a+1);i>=1;i--)
        	{ 
        		if((a*a+1)%i==0)
        		{ 
        			printf("%lld\n",a+a+i+(a*a+1)/i);
        			break;
        		}
        	}
        }
        return 0;
    }

[Power OJ 2402_ Arctan]: https://www.oj.swust.edu.cn/problem/show/2402
[20190213193502926.png]: /images/20210923/d169cfe3d3cc467192c9f05639582577.png