[数论]有理逼近

时间：2010-11-15 来源：I WILL BE BETTER.

对于一个素数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之间都不能再插入满足题意的有理分数。

这道题目没有数据规模的描述的话，可以依次枚举i和j使得i/j最逼近sqrt(p)，但是，对于大规模的数据来说，这样无疑会超时的（TLE十分严重）。

对于i/j约等于sqrt(p)来书可以转换成 j 约等于i/sqrt(p)，这样的优化，只需要一层循环的枚举就可以了，需去到大于sqrt(p)的最小值和小于sqrt(p)的最大值，不断更新最小值就可以了。

这道题的精度问题还十分重要。

#include<cstdio>
#include<cmath>
int n,p,xi,xj;
double min;
int main()
{
    scanf("%d %d\n",&p,&n);
    min=10000000.0;
    for (int i=n;i>0;i--)
    for (int j=(int)((double)i/sqrt(p))-3;j<=(int)((double)i/sqrt(p))+3;j++)
    if (i!=j)
    {
        if (j<=0||j>n)continue;
        if (sqrt(p)-(double)i/j>0&&sqrt(p)-(double)i/j-1e-7<=min)
        {
            xi=i;xj=j;
            min=sqrt(p)-((double)i/j);
        }
    }
    printf("%d/%d ",xi,xj);
    min=10000000.0;
    for (int i=n;i>0;i--)
    for (int j=(int)((double)i/sqrt(p))-3;j<=(int)((double)i/sqrt(p))+3;j++)
    if (i!=j)
    {
        if (j<=0||j>n)continue;
        if (sqrt(p)-(double)i/j<0&&(double)i/j-sqrt(p)-1e-7<=min)
        {
            xi=i;xj=j;
            min=((double)i/j)-sqrt(p);
        }
    }
    printf("%d/%d\n",xi,xj);
    return 0;
}