SPOJ :Use of Function Arctan

1540 단어
Description
It's easy to know that arctan(1/2)+arctan(1/3)=arctan(1).The problem is,to some fixed number A,you have to write a 
program to calculate the minimum sum B+C.A,B and C are all positive integers and satisfy the equation below:
arctan(1/A)=arctan(1/B)+arctan(1/C)
Input
The first line contains a integer number T.T lines follow,each contains a single integer A, 1<=A<=60000.
Output
T lines,each contains a single integer which denotes to the minimum sum B+C.
Sample Input
1
1

Sample Output
5

Hint
Some new test data has been added on Feb.15, 2009, 36 users lose their Accepted.
Source limit:    256B Languages   :    All except: C99 strict ERL JS
//분석 계산 프로세스:arctan(1/A) =arctan(1/B)+arctan(1/C), 좌우 동시에 tan의 값을 취하면 등식을 1/A=(1/B+1/C)/(1-1/B*1/C)
A=(B*C-1)/(B+C)로 계속 단순화합니다.설정 B=A+m, C=A+n 위의 표현식화 간략화 m*n=A*A+1, 요구하는 것은 B+C=2*A+m+n의
최소값, m+n>=2*sqrt(m*n)=2*sqrt(A*A+1),'='호를 얻으려면 m=n=sqrt(A*A+1)가 필요합니다. A,B,C가 모두 정수이기 때문에 m,n도 정수여야 합니다.
이때 필요한 것은 매거 m=sqrt(A*A+1)부터 1까지입니다. 첫 번째로 sqrt(A*A+1)를 제거할 수 있는 m를 얻는 것이 필요한 값입니다.시간 복잡도는 O(n)입니다.이 문제 코드 길이
제한은 변태적이다.
#include<stdio.h>
#include<math.h>
int main(){
	long long t,a,i;
	scanf("%lld",&t);
	while(t--){
		scanf("%lld",&a);
		long long i=(long long)sqrt(1.0*(a*a+1));
		while((a*a+1)%i) i--;
		printf("%lld
",2*a+i+(a*a+1)/i); } return 0; }

좋은 웹페이지 즐겨찾기