# dividing without divide
 
def divide(num, div):
    quot = 0
    while div <= num:
        quot += 1
        num -= div
    return quot, num
 
print divide(31,5)
 
def divide(num, div):
    divs, sqs, sum = [div], [1], 0
    while divs[-1] * divs[-1] < num:
        divs.append(divs[-1] * divs[-1])
        sqs.append(sqs[-1] * sqs[-1] * div)
    while divs:
        div, sq = divs.pop(), sqs.pop()
        print div, sq,
        quot = 0
        while div <= num:
            quot += 1
            num -= div
        sum += (quot * sq)
        print (quot * sq)
    return sum, num
 
print divide(1000000000,3)
print divide(31,5)

IyBkaXZpZGluZyB3aXRob3V0IGRpdmlkZQoKZGVmIGRpdmlkZShudW0sIGRpdik6CiAgICBxdW90ID0gMAogICAgd2hpbGUgZGl2IDw9IG51bToKICAgICAgICBxdW90ICs9IDEKICAgICAgICBudW0gLT0gZGl2CiAgICByZXR1cm4gcXVvdCwgbnVtCgpwcmludCBkaXZpZGUoMzEsNSkKCmRlZiBkaXZpZGUobnVtLCBkaXYpOgogICAgZGl2cywgc3FzLCBzdW0gPSBbZGl2XSwgWzFdLCAwCiAgICB3aGlsZSBkaXZzWy0xXSAqIGRpdnNbLTFdIDwgbnVtOgogICAgICAgIGRpdnMuYXBwZW5kKGRpdnNbLTFdICogZGl2c1stMV0pCiAgICAgICAgc3FzLmFwcGVuZChzcXNbLTFdICogc3FzWy0xXSAqIGRpdikKICAgIHdoaWxlIGRpdnM6CiAgICAgICAgZGl2LCBzcSA9IGRpdnMucG9wKCksIHNxcy5wb3AoKQogICAgICAgIHByaW50IGRpdiwgc3EsCiAgICAgICAgcXVvdCA9IDAKICAgICAgICB3aGlsZSBkaXYgPD0gbnVtOgogICAgICAgICAgICBxdW90ICs9IDEKICAgICAgICAgICAgbnVtIC09IGRpdgogICAgICAgIHN1bSArPSAocXVvdCAqIHNxKQogICAgICAgIHByaW50IChxdW90ICogc3EpCiAgICByZXR1cm4gc3VtLCBudW0KCnByaW50IGRpdmlkZSgxMDAwMDAwMDAwLDMpCnByaW50IGRpdmlkZSgzMSw1KQ==