Buggy python submission (verdict: Time Limit Exceeded):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)

class Flow():
    def __init__(self, e, N):
        self.E = e
        self.N = N
        self.nl = list(range(N))

    def max_flow(self, s, t):
        r = 0
        e = self.E
        v = None

        def f(c):
            v[c] = 1
            if c == t:
                return 1
            for i in e[c]:
                if v[i] is None and f(i):
                    e[c].remove(i)
                    e[i].add(c)
                    return 1
            return

        while True:
            v = [None] * self.N
            if f(s) is None:
                break
            r += 1

        return r

def main():
    rr = []

    def f(p, q, a, n):
        r = 0
        fr = fractions.Fraction(p,q)
        q = [(fr, 0, 1)]
        if fr.numerator == 1:
            r += 1
        for i in range(1, 111):
            nq = []
            ti = fractions.Fraction(1, i)
            for t, c, m in q:
                for k in range(1, n-c):
                    mik = m*i**k
                    if t <= ti * k or a < mik:
                        break
                    tt = t - ti * k
                    if tt.numerator == 1 and tt.denominator >= i and mik * tt.denominator <= a:
                        r += 1
                    if mik * (i+1) < a:
                        nq.append((tt, c+k, mik))
                if m * (i+1) < a:
                    nq.append((t,c,m))
            q = nq
        return r

    while True:
        p, q, a, n = LI()
        if p == 0 and q == 0:
            break
        rr.append(f(p, q, a, n))

    return '\n'.join(map(str, rr))



print(main())



Fixed submission:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)

def main():
    rr = []

    def f(p, q, a, n):
        r = 0
        fr = fractions.Fraction(p,q)
        q = [(fr, 0, 1)]
        if fr.numerator == 1 and fr.denominator <= a:
            r += 1
        n1 = n-1
        for i in range(1, 70):
            nq = []
            ti = fractions.Fraction(1, i)
            i2 = (i+1) ** 2
            for t, c, m in q:
                mik = m
                tt = t
                for k in range(1, n-c):
                    mik *= i
                    tt -= ti
                    if tt <= 0 or a < mik * i:
                        break
                    if tt.numerator == 1 and tt.denominator >= i and mik * tt.denominator <= a:
                        r += 1
                    if c+k < n1 and mik * (i ** max(math.ceil(tt / ti), 2)) < a:
                        nq.append((tt, c+k, mik))
                if m * (i ** max(math.ceil(t / ti), 2)) < a:
                    nq.append((t,c,m))
            if not nq:
                break
            q = nq
        return r

    while True:
        p, q, a, n = LI()
        if p == 0 and q == 0:
            break
        rr.append(f(p, q, a, n))

    return '\n'.join(map(str, rr))



print(main())

Buggy python submission (verdict: Time Limit Exceeded):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    rr = []

    def f(p, q, a, n):
        r = 0
        fr = fractions.Fraction(p,q)
        q = [(fr, 0, 1)]
        if fr.numerator == 1 and fr.denominator <= a:
            r += 1
        n1 = n-1
        for i in range(1, 111):
            nq = []
            ti = fractions.Fraction(1, i)
            i2 = (i+1) ** 2
            for t, c, m in q:
                mik = m
                tt = t
                for k in range(1, n-c):
                    mik *= i
                    tt -= ti
                    if tt <= 0 or a < mik:
                        break
                    if tt.numerator == 1 and tt.denominator >= i and mik * tt.denominator <= a:
                        r += 1
                    if c+k < n1 and mik * i2 < a:
                        nq.append((tt, c+k, mik))
                if m * i2 < a:
                    nq.append((t,c,m))
            if not nq:
                break
            q = nq
        return r

    while True:
        p, q, a, n = LI()
        if p == 0 and q == 0:
            break
        rr.append(f(p, q, a, n))

    return '\n'.join(map(str, rr))



print(main())



Fixed submission:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)

def main():
    rr = []

    def f(p, q, a, n):
        r = 0
        fr = fractions.Fraction(p,q)
        q = [(fr, 0, 1)]
        if fr.numerator == 1 and fr.denominator <= a:
            r += 1
        n1 = n-1
        for i in range(1, 70):
            nq = []
            ti = fractions.Fraction(1, i)
            i2 = (i+1) ** 2
            for t, c, m in q:
                mik = m
                tt = t
                for k in range(1, n-c):
                    mik *= i
                    tt -= ti
                    if tt <= 0 or a < mik * i:
                        break
                    if tt.numerator == 1 and tt.denominator >= i and mik * tt.denominator <= a:
                        r += 1
                    if c+k < n1 and mik * (i ** max(math.ceil(tt / ti), 2)) < a:
                        nq.append((tt, c+k, mik))
                if m * (i ** max(math.ceil(t / ti), 2)) < a:
                    nq.append((t,c,m))
            if not nq:
                break
            q = nq
        return r

    while True:
        p, q, a, n = LI()
        if p == 0 and q == 0:
            break
        rr.append(f(p, q, a, n))

    return '\n'.join(map(str, rr))



print(main())