Consider the following pseudo-code fragment in which an invariant for the loop is “ $m ^*x^k=p^n$ and $k \geq 0$ ” (here, $p$ and $n$ are integer variable that have been initialized):
/* Pre-conditions : $p \geq 1 \wedge n \geq 0$ */
/* Assume that overflow never occurs */
int $x=p$; int $k=n$; int $m=1$;
while $(k < >0)$ {
if (k is odd) then $m=m^*x$;
$x=x^*x$;
$k=\lfloor k/2 \rfloor$; /* floor$(k/2)$ */
}
Which of the following must be true ar the end of the while loop?
- $x=p^n$
- $m=p^n$
- $p=x^n$
- $p=m^n$
