描述
对于一个素数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之间都不能再插入满足题意的有理分数。
任 务 ：
给定P、N（N>sqrt(p)），求X、Y、U、V，使x/y<sqrt(p)<u/v且x/y与sqrt(p)之间、sqrt(p)与u/v之间都不能再插入满足题意的有理分数。
输入格式
输入文件的第一行为P、N，其中 P、N<30000。
输出格式
输出文件只有一行，格式为“X/Y U/V”。注意，答案必须是既约的，也就是说分子、分母的最大公约数必须等于1。
测试样例1
输入
样例1：
2 5
样例2：
5 100
输出
样例1：
4/3 3/2
样例2：
38/17 85/38
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
数论？
注意到最大值和最小值都必定是在sqrt(p)附近，所以只要枚举分母i，计算相应的分子值kkz，再用(kkz-1)/i，kkz/i，(kkz+1)/i更新maxx1和minn1值就可以了。
另外，如果分母大于n，就减到n再更新，且只用kkz/i值更新minn1。
时间复杂度……O(3*n)？
（Tyvj挂掉了……我是在CODE[VS]上测的……）
#include<cstdio>
#include<iostream>
#include<cmath>
using namespace std;int p,n;
double now,maxx1,minn1,kkzv;struct node{int x,y;
}minn,maxx;int gcd(int u,int v)
{return v ? gcd(v,u%v):u;
}int main()
{scanf("%d%d",&p,&n);now=sqrt((double)p);maxx1=999999999;for(int i=1;i<=n;i++){int kkz=i*now;if(kkz>n){while(kkz>n) kkz--;if(kkz && kkz/i>minn1 && kkz/i<now) minn1=kkz/i,minn.x=kkz,minn.y=i;continue;}if((kkz) && (kkzv=(double)kkz/i)>minn1 && kkzv<now) minn.x=kkz,minn.y=i,minn1=kkzv;else{if((kkz-1) && (kkzv=(double)(kkz-1)/i)>minn1 && kkzv<now) minn.x=(kkz-1),minn.y=i,minn1=kkzv;}if((kkz+1<=n) && (kkzv=(double)(kkz+1)/i)<maxx1 && kkzv>now) maxx.x=kkz+1,maxx.y=i,maxx1=kkzv;}if(kkzv=(maxx.x>minn.y ? gcd(maxx.x,maxx.y):gcd(maxx.y,maxx.x))) maxx.x/=kkzv,maxx.y/=kkzv;if(kkzv=(minn.x>minn.y ? gcd(minn.x,minn.y):gcd(minn.y,minn.x))) minn.x/=kkzv,minn.y/=kkzv;printf("%d/%d %d/%d\n",minn.x,minn.y,maxx.x,maxx.y);return 0;
}