codevs2190 有理逼近

codevs2190 有理逼近

题目描述 Description

对于一个素数P，我们可以用一系列有理分数(分子、分母都是不大于N的自然数)来逼近sqrt(p)，例如P=2，N=5的时候：1/1<5/4<4/3< sqrt(2)<3/2<5/3<2/1。
任　务　：
给定P、N（N>sqrt(p)），求X、Y、U、V，使x/y< sqrt(p)< u/v且x/y与sqrt(p)之间、sqrt(p)与u/v之间都不能再插入满足题意的有理分数。
输入描述 Input Description

输入文件的第一行为P、N 输出描述 Output Description

输出文件只有一行，格式为“X/Y U/V”。注意，答案必须是既约的，也就是说分子、分母的最大公约数必须等于1。

枚举分母，对于这个分母找到最接近的分子，二分查找。

#include<cstdio>
#include<cstring>
#define LL long long
int gcd(int x,int y)
{return y?gcd(y,x%y):x;
}
int main()
{int i,j,k,m,n,p,q,x,y,z,l,r,mid,la=-1,lb,ua=-1,ub;scanf("%d%d",&p,&n);for (i=1;i<=n;i++){l=1;r=n;while (l<=r){mid=(l+r)/2;if (mid*mid>(LL)p*i*i){if (gcd(i,mid)==1&&(ua==-1||mid*ua<i*ub)){ua=i;ub=mid;}r=mid-1;}else{if (gcd(i,mid)==1&&(la==-1||mid*la>i*lb)){la=i;lb=mid;}l=mid+1;}}}printf("%d/%d %d/%dn",lb,la,ub,ua);
}