TYVJ P1077

描述 Description

对于一个素数P，我们可以用一系列有理分数(分子、分母都是不大于N的自然数)来逼近sqrt(p)，例如P=2，N=5的时候：1/1<5/4& lt;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之间都不能再插入满足题意的有理分数。

输入格式 InputFormat

输入文件的第一行为P、N，其中 P、N<30000。

输出格式 OutputFormat

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

样例输入 SampleInput [复制数据]

样例1：
2 5
样例2：
5 100

样例输出 SampleOutput [复制数据]

样例1：
4/3 3/2

样例2：
38/17 85/38

思路：我采取的是O(n)的算法，for一遍1到n，然后从 x/y<sqrt(p)->x^2/y^2<p 可以大致O(1)算出这个x或者y，然后上线去x-1,x,x+1，判断即可

 1 #include <cmath>
 2 #include <cstdio>
 3 #include <algorithm>
 4 #include <cstring>
 5 #include <string>
 6 #include <cstdlib>
 7 using namespace std;
 8 
 9 const int maxn=210;
10 int x,a1,a2,b1,b2,z,n,p;
11 double y,v;
12 
13 void close()
14 {
15 exit(0);
16 }
17 
18 void judge(int x,int i)
19 {
20     if (x<=0 || x>n) return;
21 //    printf("i:%d x:%d i/x:%.4lf
",i,x,1.0*i/x);
22     if (1.0*i/x<v) //小于
23     {
24         if (1.0*i/x>1.0*a1/b1)
25         {
26             a1=i;
27             b1=x;
28 //            printf("a1:%d b1:%d a1/b1:%.4lf v:%.4lf
",a1,b1,a1/b1*1.0,v);
29         }
30     }
31     else
32     {
33         if (1.0*i/x<1.0*a2/b2)
34         {
35             a2=i;
36             b2=x;
37 //            printf("a2:%d b2:%d a2/b2:%.4lf v:%.4lf
",a2,b2,a2/b2*1.0,v);
38         }
39     }
40 }
41 
42 
43 void work(int i)
44 {
45     y=i/v*1.0;
46 //    printf("i:%d y:%.4lf
",i,y);
47     z=(int)y;
48     judge(z-1,i);
49     judge(z,i);
50     judge(z+1,i);
51 }
52 
53 void init()
54 {
55 
56     scanf("%d %d",&p,&n);
57     v=sqrt(p);
58     a1=a2=0;b1=b2=1;
59     a2=1000000;
60     for (int i=1;i<=n;i++)
61         work(i);
62     for (int i=100000;i>=1;i--)
63         if (a1 % i==0 && b1 % i==0)
64         {
65             a1/=i;
66             b1/=i;
67         }
68     for (int i=100000;i>=1;i--)
69         if (a2 % i==0 && b2 % i==0)
70         {
71             a2/=i;
72             b2/=i;
73         }
74     printf("%d/%d %d/%d
",a1,b1,a2,b2);
75 }
76 
77 int main ()
78 {
79     init();
80     close();
81     return 0;
82 }