描述
对于一个素数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，其中 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
代码
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 using namespace std; 9 int des_int,P,N,a,b,ans[10]={ 1,1,1,1,1,1,1,1,1,1};10 double des;11 12 int check(int i,int j,double x){13 return (fabs( des-double(ans[i])/double(ans[j]) ) > fabs( des-x ));14 }15 16 void xiao(){ //ans1~217 for(int i=des_int-1;i<=N;i++){18 int flag=0;19 for(int j=1;j<=i;j++){20 double x=double(i)/double(j);21 if(x>des) continue;22 if(check(1,2,x)){23 double k1=(double(ans[1])/double(ans[2])),k2=x;24 bool fl=(k1==k2);25 if(fl) continue;26 ans[1]=i;ans[2]=j;27 }28 else{29 flag=1;break;30 }31 }32 if(flag==1) continue;33 }34 }35 36 void da(){ //ans3~437 for(int i=des_int+1;i<=N;i++){38 int flag=0;39 for(int j=i-1;j>=1;j--){40 double x=double(i)/double(j);41 if(x 穷尽今生所学，T掉2个点
上看不懂的别人代码：
1 #include2 #include 3 #include 4 5 int main(int argc, char **argv) 6 { 7 int i, j; 8 int p, n; 9 int a, b, c, d;10 int beg, end;11 double s, max = 0, min = 300000, t;12 scanf("%d%d", &p, &n);13 s = sqrt(p);14 for(i = 1; i <= n; i++){15 beg = i * s - 1;16 end = beg + 1;17 if(beg <= 0){18 beg = 1;19 }20 if(end > n){21 end = n;22 }23 for(j = beg; j <= end; j++){24 t = (double)(j) / i;25 if(t < s && t > max){26 a = j, b = i;27 max = t;28 }29 }30 }31 for(i = 1; i <= n; i++){32 beg = i * s;33 end = beg + 1;34 if(beg <= 0){35 beg = 0;36 }37 if(end > n){38 end = n;39 }40 for(j = beg; j <= end; j++){41 t = (double)(j) / i;42 if(t > s && min > t){43 c = j, d = i;44 min = t;45 }46 }47 }48 printf("%d/%d %d/%d\n", a, b, c, d);49 return 0;50 }
---------------我是猥琐的分割线---------------
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 using namespace std; 9 int des_int,P,N,a,b,ans[10]={ 1,1,1,1,1,1,1,1,1,1};10 double des;11 12 int check(int i,int j,double x){13 return (fabs( des-double(ans[i])/double(ans[j]) ) > fabs( des-x ));14 }15 16 void xiao(){ //ans1~217 for(int i=des_int-1;i<=N;i++){18 int flag=0;19 for(int j=1;j<=i;j++){20 double x=double(i)/double(j);21 if(x>des) continue;22 if(check(1,2,x)){23 double k1=(double(ans[1])/double(ans[2])),k2=x;24 bool fl=(k1==k2);25 if(fl) continue;26 ans[1]=i;ans[2]=j;27 }28 else{29 flag=1;break;30 }31 }32 if(flag==1) continue;33 }34 }35 36 void da(){ //ans3~437 for(int i=des_int+1;i<=N;i++){38 int flag=0;39 for(int j=des_int/i+1000;j>=1;j--){40 double x=double(i)/double(j);41 if(x 39行调了个阈值成功骗分，主要都是da（）函数耗的时间，也就没多想，+500有点危险，+100绝对过不了
想法来源于（能跑这么久的数肯定很大，分母也就没必要那么大了！！！）