fork(1) download
  1. import java.io.*;
  2. import java.util.*;
  3.  
  4. class Solution {
  5.  
  6. public static void main(String[] args) {
  7. Scanner in = new Scanner(System.in);
  8. int X = in.nextInt(), N = in.nextInt();
  9. int[] count = new int[X+1];
  10. count[0] = 1;
  11. ArrayList<Integer> list = new ArrayList<>();
  12. int cur = 1, p = 1;
  13. while((p = pow(cur++, N))<= X)list.add(p);
  14. for(int i:list)for(int j = X-i; j>=0; j--)count[j+i] += count[j];
  15.  
  16. System.out.println(count[X]);
  17. }
  18.  
  19. static int pow(int i, int p){
  20. int out = 1;
  21. while(p>0){
  22. if(p%2==1)out *= i;
  23. i = i*i;
  24. p>>=1;
  25. if(out>1000)return 1000000;
  26. }
  27. return out;
  28. }
  29. }
Success #stdin #stdout 0.12s 29448KB
stdin
100 2
stdout
3