【Tyvj1077】有理逼近

2014-05-16
竞赛题解 / 数论
TYVJ

描述 Description

对于一个素数 P，我们可以用一系列有理分数 (分子、分母都是不大于 N 的自然数) 来逼近 sqrt(p)，例如 P=2，N=5 的时候：1/1<5/4<4/3sqrt(p)），求 X、Y、U、V，使 x/y ## 输入格式 InputFormat 输入文件的第一行为 P、N，其中 P、N<30000。

输出格式 OutputFormat

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

样例输入 SampleInput

29009 20000

样例输出 SampleOutput

4258/25 17543/103

Tyvj 1077

代码 Code

注意比较大小的时候要用 long double。

#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
int i,j,t,n,m,p,k,u,v,z,y,x;
long double a,b,l,r;
int gcd(int a,int b)
{
    if (b==0) return a;
    else return gcd(b,a%b);
}
int main()
{
    scanf("%d%d",&p,&n);
    a=0;b=27110000.00;
    for (k=1;k<=n;k++)
    {
        m=(int)sqrt(k*k/p)+1;
        t=gcd(k,m);
        l=(double)k/m;
        if (l<=sqrt(p) && l>a)
        {
            a=l;
            x=k/t;
            y=m/t;
        }
        t=gcd(k,m-1);
        r=(double)k/(m-1);
        if (r>=sqrt(p) && r<b)
        {
            b=r;
            u=k/t;
            v=(m-1)/t;
        }
    }
    printf("%d/%d %d/%d\n",x,y,u,v);
    return 0;
}