THIS DOES NOT WORK FOR SOME VALUES.. IF YOU HAVE A CLUE PLEASE HELP
Java - 124 bytes
int p(int a,int b){int c=0,t=a;double p;while(t>0){if(a-(p=Math.pow(t,b))>=0){while((a-=p)>=0){c++;}a+=p;}t--;}return c+=a;}
Ungolfed
int p(int a, int b){
int c=0,t=a;
double p;
while (t>0){
if (a-(p=Math.pow(t, b))>=0){
while((a-=p)>=0){
c++;
}
a+=p;
}
t--;
}
return c+=a;
}
Result
System.out.println(p(7, 2)); // 4
System.out.println(p(4,2)); // 1
System.out.println(p(7,3)); // 7
System.out.println(p(23,3)); // 9