Разложение числа на сумму k ых степеней натурального числа

import java.util.Scanner;
 
public class Solution {
    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        int n = s.nextInt();
        int k = s.nextInt();
 
        int count = 0;
        while (n > 0) {
            int x = sqrt(n, k);
            n -= pow(x, k);
            ++count;
        }
        System.out.println(count);
    }
 
    // Нахождение корня n-ой степени
    public static int sqrt(int base, int sqrtPow) {
        return (int) Math.pow(base, 1.0 / sqrtPow);
    }
    
    public static int pow(int base, int pow) {
        return (int) Math.pow(base, pow);
    }
}

import java.util.Scanner;
 
public class Solution {
    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        int n = s.nextInt();
        int k = s.nextInt();
        
        long start = System.nanoTime();
        
        int[] z = new int[n + 1];
 
        z[0] = 0;
        
        for (int i = 1; i <= n; ++i) {
            if (wholeRoot(i, k)) {
                z[i] = 1;
            } else {
                int min = Integer.MAX_VALUE;
                
                for(int j=1; j <= i/2; ++j) {
                    min = Math.min(min, z[j] + z[i-j]);
                }
                
                z[i] = min;
            }
        }
        
        System.out.println(z[n]);
        System.out.println((System.nanoTime() - start)/(1_000_000_000.0));
    }
 
    public static boolean wholeRoot(int a, int k) {
        return Math.pow(a, 1.0 / k) == (int) Math.pow(a, 1.0 / k);
    }
}