Aizu Online Judge 1208 Rational Irrationals

■1208 Rational Irrationals

全探索を行うと，O(n²)でかなりキツイ．そこで二部探索を使う．
具体的には，分数をm/dとした時，dを1~nまで回し，√pに近くなるようなmを求める．
探索の幅として[1,n]を設定し，m/d<√pを条件とすれば，
m/d<√p<(m+1)/d
もしくは，
m/d<(m+1)/d<√p (ただし，m+1>n)
となる．
事実上計算量はO(n)．

view plainprint?

1. import java.util.*;  
2. import java.lang.*;  
3. import java.math.*;  
4. import java.io.*;  
5.   
6. import static java.lang.Math.*;  
7. import static java.util.Arrays.*;  
8.   
9. public class Main{  
10.   
11.  Scanner sc=new Scanner(System.in);  
12.   
13.  int INF=1<<28;  
14.  double EPS=1e-9;  
15.   
16.  int p, m;  
17.   
18.  void run(){  
19.   for(;;){  
20.    p=sc.nextInt();  
21.    m=sc.nextInt();  
22.    if((p|m)==0){  
23.     break;  
24.    }  
25.    solve();  
26.   }  
27.  }  
28.   
29.  void solve(){  
30.   long n1=0, d1=1;  
31.   long n2=m, d2=1;  
32.   for(long d=1; d<=m; d++){  
33.    double left=1, right=m;  
34.    for(int i=0; i<100; i++){  
35.     double mid=(left+right)/2;  
36.     if(mid*mid<p*d*d+EPS){  
37.      left=mid;  
38.     }else{  
39.      right=mid;  
40.     }  
41.    }  
42.    int n=(int)(left+EPS);  
43.    if(n1*d<n*d1&&n*n<p*d*d){  
44.     n1=n;  
45.     d1=d;  
46.    }  
47.    if(++n<=m){  
48.     if(p*d*d<n*n&&n*d2<n2*d){  
49.      n2=n;  
50.      d2=d;  
51.     }  
52.    }  
53.   }  
54.   long gcd=gcd(n1, d1);  
55.   n1/=gcd;  
56.   d1/=gcd;  
57.   gcd=gcd(n2, d2);  
58.   n2/=gcd;  
59.   d2/=gcd;  
60.   println(n2+"/"+d2+" "+n1+"/"+d1);  
61.  }  
62.   
63.  long gcd(long m, long n){  
64.   for(; n!=0;){  
65.    m=m%n;  
66.    long t=m;  
67.    m=n;  
68.    n=t;  
69.   }  
70.   return m;  
71.  }  
72.   
73.  void debug(Object... os){  
74.   System.err.println(Arrays.deepToString(os));  
75.  }  
76.   
77.  void print(String s){  
78.   System.out.print(s);  
79.  }  
80.   
81.  void println(String s){  
82.   System.out.println(s);  
83.  }  
84.   
85.  public static void main(String[] args){  
86.   // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
87.   new Main().run();  
88.  }  
89. }  

import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class Main{

 Scanner sc=new Scanner(System.in);

 int INF=1<<28;
 double EPS=1e-9;

 int p, m;

 void run(){
  for(;;){
   p=sc.nextInt();
   m=sc.nextInt();
   if((p|m)==0){
    break;
   }
   solve();
  }
 }

 void solve(){
  long n1=0, d1=1;
  long n2=m, d2=1;
  for(long d=1; d<=m; d++){
   double left=1, right=m;
   for(int i=0; i<100; i++){
    double mid=(left+right)/2;
    if(mid*mid<p*d*d+EPS){
     left=mid;
    }else{
     right=mid;
    }
   }
   int n=(int)(left+EPS);
   if(n1*d<n*d1&&n*n<p*d*d){
    n1=n;
    d1=d;
   }
   if(++n<=m){
    if(p*d*d<n*n&&n*d2<n2*d){
     n2=n;
     d2=d;
    }
   }
  }
  long gcd=gcd(n1, d1);
  n1/=gcd;
  d1/=gcd;
  gcd=gcd(n2, d2);
  n2/=gcd;
  d2/=gcd;
  println(n2+"/"+d2+" "+n1+"/"+d1);
 }

 long gcd(long m, long n){
  for(; n!=0;){
   m=m%n;
   long t=m;
   m=n;
   n=t;
  }
  return m;
 }

 void debug(Object... os){
  System.err.println(Arrays.deepToString(os));
 }

 void print(String s){
  System.out.print(s);
 }

 void println(String s){
  System.out.println(s);
 }

 public static void main(String[] args){
  // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
  new Main().run();
 }
}