PKU Judge Online 3100 Root of the Problem

■3100 Root of the Problem

□Problem
整数b，nが与えられる．aⁿがbと最も近くなるような整数aを求めよ．

□Solution
a=e^log(b)/n
なので，上式で近そうな値をとり，その周辺を探す．

□Code

view plainprint?

1. package p3100;  
2.   
3. import java.util.*;  
4. import java.lang.*;  
5. import java.math.*;  
6. import java.io.*;  
7.   
8. import static java.lang.Math.*;  
9. import static java.util.Arrays.*;  
10.   
11. // AC  
12. public class Main{  
13.   
14.     Scanner sc=new Scanner(System.in);  
15.   
16.     final int INF=Integer.MAX_VALUE;  
17.     final double EPS=1e-9;  
18.   
19.     void run(){  
20.         for(;;){  
21.             int b=sc.nextInt();  
22.             int n=sc.nextInt();  
23.             if(b==0&&n==0)  
24.                 break;  
25.             int a=(int)Math.exp(Math.log(b)/n);  
26.             a--;  
27.             int ans=a;  
28.             double ansPowN=Math.pow(ans, n);  
29.             for(int i=a;; i++){  
30.                 double iPowN=Math.pow(i, n);  
31.                 if(Math.abs(b-iPowN)<Math.abs(b-ansPowN)){  
32.                     ans=i;  
33.                     ansPowN=iPowN;  
34.                 }  
35.                 if(iPowN>b){  
36.                     break;  
37.                 }  
38.             }  
39.             println(ans+"");  
40.         }  
41.     }  
42.   
43.     void print(String s){  
44.         System.out.print(s);  
45.     }  
46.   
47.     void println(String s){  
48.         System.out.println(s);  
49.     }  
50.   
51.     public static void main(String[] args){  
52.         // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
53.         new Main().run();  
54.     }  
55. }  

package p3100;

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

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

// AC
public class Main{

    Scanner sc=new Scanner(System.in);

    final int INF=Integer.MAX_VALUE;
    final double EPS=1e-9;

    void run(){
        for(;;){
            int b=sc.nextInt();
            int n=sc.nextInt();
            if(b==0&&n==0)
                break;
            int a=(int)Math.exp(Math.log(b)/n);
            a--;
            int ans=a;
            double ansPowN=Math.pow(ans, n);
            for(int i=a;; i++){
                double iPowN=Math.pow(i, n);
                if(Math.abs(b-iPowN)<Math.abs(b-ansPowN)){
                    ans=i;
                    ansPowN=iPowN;
                }
                if(iPowN>b){
                    break;
                }
            }
            println(ans+"");
        }
    }

    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();
    }
}