# -*- coding: utf-8 -*-
"""
Created on Tue Jan 14 19:17:56 2014

@author: dconduche
"""

def Mystere(x,n) : # x et n sont des entiers
    res=1
    while n>0 :
        if n%2==1 :
            res=res*x
        n=n//2
        x=x*x
    return res

def Mystere_d(x,n) : # x et n sont des entiers
    res=1
    k=0             #Compteur des passages dans la boucle
    x0=x
    n0=n
    invariant=(res*(x**n)==x0**n0) #Invariant
    print('Invariant : res*(x**n)==x0**n0')
    print('Invariant='+str(invariant)+', passage : '+str(k)+' x='+str(x)+' n='+str(n)+' res='+str(res))
    while n>0 :
        if n%2==1 :
            res=res*x
        n=n//2
        x=x*x
        k=k+1
        invariant=(res*(x**n)==x0**n0) #Invariant
        print('Invariant='+str(invariant)+', passage : '+str(k)+' x='+str(x)+' n='+str(n)+' res='+str(res))
    return res

#Tests
print(Mystere_d(3,3))
print(Mystere_d(2,10))
print(Mystere_d(2,100))