# 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)