Problem:


Problem C: Unit Fraction Partition

A fraction whose numerator is 1
and whose denominator is a positive integer
is called a unit fraction.
A representation of a positive rational number
p/q
as the sum of finitely many unit fractions is called a partition of
p/q
into unit fractions.
For example,
1/2 + 1/6
is a partition of
2/3
into unit fractions.
The difference in the order of addition is disregarded.
For example, we do not distinguish
1/6 + 1/2
from
1/2 + 1/6.

For given four positive integers
p,
q,
a, and
n,
count the number
of partitions of
p/q
into unit fractions satisfying the following two conditions.

The partition is the sum of at most
n
many unit fractions.

The product of the denominators of the unit fractions in the
partition is less than or equal to
a.

For example, if
(p,q,a,n) = (2,3,120,3),
you should report 4 since

enumerates all of the valid partitions.

Input

The input is a sequence of at most 1000 data sets followed by a terminator.

A data set is a line containing four positive integers
p,
q,
a, and
n
satisfying
p,q <= 800,
a <= 12000
and
n <= 7.
The integers are separated by a space.

The terminator is composed of just one line
which contains four zeros separated by a space.
It is not a part of the input data but a mark for the end of the input.

Output

The output should be composed of lines
each of which contains a single integer.
No other characters should appear in the output.

The output integer corresponding to a data set
p,
q,
a,
n
should be the number of all partitions of
p/q
into at most
n
many unit fractions such that the product of the denominators of the
unit fractions is less than or equal to
a.

Sample Input

2 3 120 3
2 3 300 3
2 3 299 3
2 3 12 3
2 3 12000 7
54 795 12000 7
2 3 300 1
2 1 200 5
2 4 54 2
0 0 0 0

Output for the Sample Input

4
7
6
2
42
1
0
9
3



Sample input:
2 3 120 3
2 3 300 3
2 3 299 3
2 3 12 3
2 3 12000 7
54 795 12000 7
2 3 300 1
2 1 200 5
2 4 54 2
0 0 0 0


Sample output:
4
7
6
2
42
1
0
9
3

Submission status: Time Limit Exceeded

Solution code:
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())

Submission status: Time Limit Exceeded

Solution code:
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())

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
def solve(p, q, a, n, l=1):

    if n==1:
        #print(p, q, a, n, l, 1 if p==1 and q<=a and q>=l else 0)
        return 1 if p==1 and q<=a and q>=l else 0
    ans = 0
    if p==1 and q<=a and q>=l:
        ans += 1
    denom = l if p==0 else max(l, int(q/p))
    while n*q >= denom*p and denom <= a:  #n/denom >= p/q:
        p_, q_ = p*denom-q, q*denom
        if p_ <= 0:
            denom += 1
            continue
        gcd_ = gcd(p_, q_)
        p_ //= gcd_
        q_ //= gcd_
        ans += solve(p_, q_, a//denom, n-1, denom)

        denom += 1
    #print(p, q, a, n, l, ans)
    return ans

while True:
    p, q, a, n = map(int, input().split())
    if p==q==a==n==0:
        break
    gcd_ = gcd(p, q)
    p //= gcd_
    q //= gcd_
    print(solve(p, q, a, n))

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
from functools import lru_cache
@lru_cache(maxsize=None)
def solve(p, q, a, n, l=1):

    if n==1:
        #print(p, q, a, n, l, 1 if p==1 and q<=a and q>=l else 0)
        return 1 if p==1 and q<=a and q>=l else 0
    ans = 1 if p==1 and q<=a and q>=l else 0
    denom = l if p==0 else max(l, int(q/p))
    while n*q >= denom*p and denom <= a:  #n/denom >= p/q:
        p_, q_ = p*denom-q, q*denom
        if p_ <= 0:
            denom += 1
            continue
        gcd_ = gcd(p_, q_)
        p_ //= gcd_
        q_ //= gcd_
        ans += solve(p_, q_, a//denom, n-1, denom)

        denom += 1
    #print(p, q, a, n, l, ans)
    return ans

while True:
    p, q, a, n = map(int, input().split())
    if p==q==a==n==0:
        break
    gcd_ = gcd(p, q)
    p //= gcd_
    q //= gcd_
    print(solve(p, q, a, n))

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
from functools import lru_cache
@lru_cache(maxsize=None)
def solve(p, q, a, n, l=1):

    #if n==1:
    #    #print(p, q, a, n, l, 1 if p==1 and q<=a and q>=l else 0)
    #    return 1 if p==1 and q<=a and q>=l else 0
    ans = 1 if p==1 and q<=a and q>=l else 0
    denom = l if p==0 else max(l, int(q/p))
    while n*q >= denom*p and denom <= a:  #n/denom >= p/q:
        p_, q_ = p*denom-q, q*denom
        if p_ <= 0:
            denom += 1
            continue
        gcd_ = gcd(p_, q_)
        p_ //= gcd_
        q_ //= gcd_
        if n==2 and p_==1 and q_*denom<=a and q_>=denom:
            ans += 1
        else:
            ans += solve(p_, q_, a//denom, n-1, denom)

        denom += 1
    #print(p, q, a, n, l, ans)
    return ans

while True:
    p, q, a, n = map(int, input().split())
    if p==q==a==n==0:
        break
    gcd_ = gcd(p, q)
    p //= gcd_
    q //= gcd_
    if n==1:
        print(1 if p==1 and q<=a else 0)
    else:
        print(solve(p, q, a, n))

Submission status: Time Limit Exceeded

Solution code:

from fractions import gcd

def solve(p, q, a, n, l=1):

    #if n==1:
    #    #print(p, q, a, n, l, 1 if p==1 and q<=a and q>=l else 0)
    #    return 1 if p==1 and q<=a and q>=l else 0
    ans = 1 if p==1 and q<=a and q>=l else 0
    denom = l if p==0 else max(l, int(q/p))
    while n*q >= denom*p and denom <= a:  #n/denom >= p/q:
        p_, q_ = p*denom-q, q*denom
        if p_ <= 0:
            denom += 1
            continue
        gcd_ = gcd(p_, q_)
        p_ //= gcd_
        q_ //= gcd_
        if n==2 and p_==1 and q_*denom<=a and q_>=denom:
            ans += 1
        else:
            ans += solve(p_, q_, a//denom, n-1, denom)

        denom += 1
    #print(p, q, a, n, l, ans)
    return ans

while True:
    p, q, a, n = map(int, input().split())
    if p==q==a==n==0:
        break
    gcd_ = gcd(p, q)
    p //= gcd_
    q //= gcd_
    if n==1:
        print(1 if p==1 and q<=a else 0)
    else:
        print(solve(p, q, a, n))

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd

def solve(p, q, a, n, l=1):

    #if n==1:
    #    #print(p, q, a, n, l, 1 if p==1 and q<=a and q>=l else 0)
    #    return 1 if p==1 and q<=a and q>=l else 0
    ans = 1 if p==1 and q<=a and q>=l else 0
    #denom = l if p==0 else max(l, int(q/p))
    for denom in range(max(l, int(q/p)), a+1):  #n/denom >= p/q:
        if n*q < denom*p: break
        p_, q_ = p*denom-q, q*denom
        if p_ <= 0:
            denom += 1
            continue
        gcd_ = gcd(p_, q_)
        p_ //= gcd_
        q_ //= gcd_
        if n==2 and p_==1 and q_*denom<=a and q_>=denom:
            ans += 1
        else:
            ans += solve(p_, q_, a//denom, n-1, denom)

        denom += 1
    #print(p, q, a, n, l, ans)
    return ans

while True:
    p, q, a, n = map(int, input().split())
    if p==q==a==n==0:
        break
    gcd_ = gcd(p, q)
    p //= gcd_
    q //= gcd_
    if n==1:
        print(1 if p==1 and q<=a else 0)
    else:
        print(solve(p, q, a, n))

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd

def solve(p, q, a, n, l=1):
    ans = 1 if p==1 and q<=a and q>=l else 0
    denom = max(l, int(q/p))
    p_denom = denom*p
    while n*q >= p_denom and denom <= a:  #n/denom >= p/q:
        p_, q_ = p_denom-q, q*denom
        if p_ <= 0:
            denom += 1
            p_denom += p
            continue
        gcd_ = gcd(p_, q_)
        p_ //= gcd_
        q_ //= gcd_
        if n==2 and p_==1 and q_*denom<=a and q_>=denom:
            ans += 1
        else:
            ans += solve(p_, q_, a//denom, n-1, denom)
        denom += 1
        p_denom += p
    #print(p, q, a, n, l, ans)
    return ans

while True:
    p, q, a, n = map(int, input().split())
    if p==q==a==n==0:
        break
    gcd_ = gcd(p, q)
    p //= gcd_
    q //= gcd_
    if n==1:
        print(1 if p==1 and q<=a else 0)
    else:
        print(solve(p, q, a, n))

Submission status: Time Limit Exceeded

Solution code:
def dfs(n, d, prod, total):
    global p, q, a

    cnt = 0

    i = d
    while prod * i <= a:
        left = p * (prod * i)
        right = total * i + prod

        if left < right * q:
            i += 1
            continue
        if left == right * q:
            cnt += 1
            i += 1
            continue
        if n == 1:
            i += 1
            continue
        cnt += dfs(n - 1, i, prod * i, right)
        i += 1
    return cnt

while True:
    p, q, a, n = map(int, raw_input().split())

    if p == 0:
        break

    print dfs(n, 1, 1, 0)

Submission status: Time Limit Exceeded

Solution code:
def dfs(n, d, prod, total):
    global p, q, a

    cnt = 0

    i = d
    while prod * i <= a:
        left = p * (prod * i)
        right = total * i + prod

        if left < right * q:
            break
        if left == right * q:
            cnt += 1
            i += 1
            continue
        if n == 1:
            i += 1
            continue
        cnt += dfs(n - 1, i, prod * i, right)
        i += 1
    return cnt

while True:
    p, q, a, n = map(int, raw_input().split())

    if p == 0:
        break

    print dfs(n, 1, 1, 0)

Submission status: Time Limit Exceeded

Solution code:
def dfs(n, d, prod, total):
    global p, q, a
    cnt = 0

    if n == 0:
        return 1

    i = d
    while prod * i <= a:
        left = p * (prod * i)
        right = total * i + prod

        if left < right * q:
            i += 1
            continue
        if left == right * q:
            cnt += 1
            i += 1
            continue
        if n == 1:
            i += 1
            continue
        cnt += dfs(n - 1, i, prod * i, right)
        i += 1
    return cnt

while True:
    p, q, a, n = map(int, raw_input().split())

    if p == 0:
        break

    print dfs(n, 1, 1, 0)

Submission status: Time Limit Exceeded

Solution code:
from fractions import Fraction
def solve(p, q, a, n):
    def _solve(f, n, m, s):
        if f < 0 or m > a or n < 0:
            return 0
        if f == 0:
            return 1
        return sum((_solve(f-Fraction(1, i), n-1, m*i, i) for i in range(s, a//m+1)), 0)
    return _solve(Fraction(p, q), n, 1, 1)
        
if __name__ == "__main__":
    while True:
        p, q, a, n = [int(i) for i in input().split()]
        if p == 0:
            break
        print(solve(p, q, a, n))

Submission status: Time Limit Exceeded

Solution code:
def solve(p, q, a, n):
    def _solve(num, dem, d, m, s):
        if p * dem == q * num:
            return 1
        if p * dem < q * num or d == 0 or dem * s ** d > a:
            return 0
        if p * dem * s - num * q * s > d * q * dem:
            return 0
        return sum((_solve(num*i+dem, dem*i, d-1, m*i, i) for i in range(s, a//m+1)), 0)
    return _solve(0, 1, n, 1, 1)
        
if __name__ == "__main__":
    while True:
        p, q, a, n = [int(i) for i in input().split()]
        if p == 0:
            break
        print(solve(p, q, a, n))

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache
from fractions import Fraction

@lru_cache(maxsize=1<<10)
def solve(p, q, a, n):
    def _solve(f, d, m, s):
        if f == 0:
            return 1
        if d == 0:
            return 0
        if f < Fraction(1, a//m):
            return 0
        return sum((_solve(f-Fraction(1, i), d-1, m*i, i)
                    for i in range(s, min(f.denominator*n//f.numerator, a//m)+1)), 0)
    return _solve(Fraction(p, q), n, 1, 1)

if __name__ == "__main__":
    while True:
        p, q, a, n = [int(i) for i in input().split()]
        if p == 0:
            break
        print(solve(p, q, a, n))

Submission status: Time Limit Exceeded

Solution code:
def f(b,x,y,c):
    global p,q,n,a
    if b==n:return 0
    ret=0
    for i in range(1,c+1):
        d=x*i+y
        e=y*i
        if e>a:break
        if p*e==q*d:ret+=1
        if p*e>q*d:ret+=f(b+1,d,e,i)
    return ret

while 1:
    p,q,a,n=map(int,input().split())
    if n==0:break
    print(f(0,0,1,a))

Submission status: Time Limit Exceeded

Solution code:
from fractions import Fraction

def frac(n):
    return(Fraction(1,n))

def part(s,a,n,m):
    if s == 0:
        return(1)
    k = int(1/s)
    if n == 1:
        if frac(k) == s and k <= a:
            return(1)
        else:
            return(0)
    else:
        ans = 0
        for i in range(max(k,m),min(a,int(n/s))+1):
            ans += part(s-frac(i), a//i, n-1, i)
        return(ans)

while(True):
    tmp = list(map(int, input().split()))
    p,q,a,n = tmp[0],tmp[1],tmp[2],tmp[3]
    if p == 0:
        quit()
    s = Fraction(p,q)
    print(part(s,a,n,1))

Submission status: Time Limit Exceeded

Solution code:
from fractions import Fraction

def frac(n):
    return(Fraction(1,n))

def part(s,a,n,m):
    if a == 0:
        return(0)
    if s == 0:
        return(1)
    k = int(1/s)
    if n == 1:
        if frac(k) == s and k <= a:
            return(1)
        else:
            return(0)
    else:
        ans = 0
        for i in range(max(k,m),min(a,int(n/s))+1):
            if s-frac(i) >= 0:
                ans += part(s-frac(i), a//i, n-1, i)
        return(ans)

while(True):
    tmp = list(map(int, input().split()))
    p,q,a,n = tmp[0],tmp[1],tmp[2],tmp[3]
    if p == 0:
        quit()
    s = Fraction(p,q)
    print(part(s,a,n,1))

Submission status: Time Limit Exceeded

Solution code:
from fractions import Fraction

def frac(n):
    return(Fraction(1,n))

def part(s,a,n,m):
    if s == 0:
        return(1)
    k = int(1/s)
    if n == 1:
        if frac(k) == s and k <= a:
            return(1)
        else:
            return(0)
    else:
        ans = 0
        for i in range(max(k,m),min(a,int(n/s))+1):
            t = s-frac(i)
            if t == 0:
                ans += 1
            elif t>0:
                ans += part(s-frac(i), a//i, n-1, i)
        return(ans)

while(True):
    tmp = list(map(int, input().split()))
    p,q,a,n = tmp[0],tmp[1],tmp[2],tmp[3]
    if p == 0:
        quit()
    s = Fraction(p,q)
    print(part(s,a,n,1))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

result = 0

def dfs(num, dem, k, cur_num, p, q, a, n):
    global result
    #print num, dem, k, cur_num
    #time.sleep(0.5)
    if (num * q) == (dem * p):
        result += 1
        #print "result: " + str(result)
        return

    if k == n:
        return

    if (num * q) > (dem * p):
        return

    i = cur_num
    while i * dem <= a:
        dfs((num * i) + dem, dem * i, k + 1, i, p, q, a, n)
        i += 1

    return

def func():
    while True:
        global result
        p, q, a, n = map(int, raw_input().split())

        if p == 0 and q == 0 and a == 0 and n == 0:
            break

        result = 0
        dfs(0, 1, 0, 1, p, q, a, n)
        print result
        
    return None

if __name__ == '__main__':
    func()

Submission status: Accepted

Solution code:
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())

Submission status: Accepted

Solution code:
from functools import lru_cache

@lru_cache(maxsize=1<<10)
def solve(p,q,a,n):
  def _solve(num,dem,d,m,s):
    if num==0:
      return 1
    if d == 0:
      return 0
    if num * a //m < dem:
      return 0
    return sum((_solve(num*i-dem, dem*i, d-1, m*i, i) for i in range(s, min(dem*n//num, a//m)+1)),0)
  return _solve(p,q,n,1,1)
ans=[]
while True:
  p,q,a,n=map(int,input().split())
  if p==0:
    break
  ans.append(solve(p,q,a,n))
print(*ans, sep="\n")

Submission status: Accepted

Solution code:
from fractions import gcd

def solve(p, q, a, n, l=1):
    ans = 1 if p==1 and q<=a and q>=l else 0
    denom = max(l, q//p)
    p_denom = denom*p
    while n*q >= p_denom and denom <= a:  #n/denom >= p/q:
        p_, q_ = p_denom-q, q*denom
        if p_ <= 0:
            denom += 1
            p_denom += p
            continue
        gcd_ = gcd(p_, q_)
        p_ //= gcd_
        q_ //= gcd_
        if n==2 and p_==1 and q_*denom<=a and q_>=denom:
            ans += 1
        else:
            ans += solve(p_, q_, a//denom, n-1, denom)
        denom += 1
        p_denom += p
    #print(p, q, a, n, l, ans)
    return ans

while True:
    p, q, a, n = map(int, input().split())
    if p==q==a==n==0:
        break
    gcd_ = gcd(p, q)
    p //= gcd_
    q //= gcd_
    if n==1:
        print(1 if p==1 and q<=a else 0)
    else:
        print(solve(p, q, a, n))

Submission status: Accepted

Solution code:
from functools import lru_cache

@lru_cache(maxsize=1<<10)
def solve(p, q, a, n):
    def _solve(num, dem, d, m, s):
        if num == 0:
            return 1
        if d == 0:
            return 0
        if num * a // m < dem:
            return 0
        return sum((_solve(num*i-dem, dem*i, d-1, m*i, i)
                    for i in range(s, min(dem*n//num, a//m)+1)), 0)
    return _solve(p, q, n, 1, 1)

if __name__ == "__main__":
    ans = []
    while True:
        p, q, a, n = [int(i) for i in input().split()]
        if p == 0:
            break
        ans.append(solve(p, q, a, n))
    print(*ans, sep="\n")

Submission status: Accepted

Solution code:
from functools import lru_cache

@lru_cache(maxsize=1<<10)
def solve(p, q, a, n):
    def _solve(num, dem, d, m, s):
        if num == 0:
            return 1
        if d == 0:
            return 0
        if num * a // m < dem:
            return 0
        return sum((_solve(num*i-dem, dem*i, d-1, m*i, i)
                    for i in range(s, min(dem*n//num, a//m)+1)), 0)
    return _solve(p, q, n, 1, 1)

if __name__ == "__main__":
    ans = []
    while True:
        p, q, a, n = [int(i) for i in input().split()]
        if p == 0:
            break
        ans.append(solve(p, q, a, n))
    print(*ans, sep="\n")

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

def dfs(num, dem, k, cur_num, prd, p, q, a, n):

    #print num, dem, k, cur_num, prd
    #time.sleep(0.5)
    if num == 0:
        #print "result: " + str(result)
        return 1

    result = 0

    i = cur_num
    while prd * i <= a:
        #print i, num, dem, k, cur_num, prd
        if (n - k) * dem < num * i:
            break
        if num * i < dem:
            i += 1
            continue

        result += dfs((num * i) - dem, dem * i, k + 1, i, prd * i, p, q, a, n)
        i += 1

    return result

def func():
    while True:

        p, q, a, n = map(int, raw_input().split())

        if p == 0 and q == 0 and a == 0 and n == 0:
            break

        print dfs(p, q, 0, 1, 1, p, q, a, n)
        
    return None

if __name__ == '__main__':
    func()

Submission status: Runtime Error

Solution code:
from fractions import Fraction

def frac(n):
    return(Fraction(1,n))

def part(s,a,n,m):
    if s == 0:
        return(1)
    k = int(1/s)
    if n == 1:
        if frac(k) == s and k <= a:
            return(1)
        else:
            return(0)
    else:
        ans = 0
        for i in range(max(k,m),min(a,int(n/s))+1q):
            ans += part(s-frac(i), a//i, n-1, i)
        return(ans)

while(True):
    tmp = list(map(int, input().split()))
    p,q,a,n = tmp[0],tmp[1],tmp[2],tmp[3]
    if p == 0:
        quit()
    s = Fraction(p,q)
    print(part(s,a,n,1))

Submission status: Runtime Error

Solution code:
EPS = 10**(-8)

def f(i, cnt, total, prod):
    global p,q,a,n
    #print p,q,a,n
    #print p/float(q), i, cnt, total, prod
    if(abs(total-p/float(q))<EPS):
        return 1
    if(total+(n-cnt)*1.0/i+EPS<p/float(q) or p/float(q)<total-EPS
       or cnt+1>n or prod*i>a):
        return 0
    return f(i,cnt+1,total+1.0/i,prod*i) + f(i+1,cnt,total,prod)

while 1:
    p,q,a,n = map(int, raw_input().split())
    if not (p or q or a or n): break
    #print p,q,a,n
    print f(1, 0, 0, 1)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-

def dfs(num, dem, k, cur_num, prd, p, q, a, n):

    #print num, dem, k, cur_num, prd
    #time.sleep(0.5)
    if num == 0:
        #print "result: " + str(result)
        return 1

    result = 0

    i = cur_num
    while prd * i <= a:
        #print i, num, dem, k, cur_num, prd
        if (n - k) * dem < num * i:
            break
        #if num * i < dem:
        #   i += 1
        #    continue

        result += dfs((num * i) - dem, dem * i, k + 1, i, prd * i, p, q, a, n)
        i += 1

    return result

def func():
    while True:

        p, q, a, n = map(int, raw_input().split())

        if p == 0 and q == 0 and a == 0 and n == 0:
            break

        print dfs(p, q, 0, 1, 1, p, q, a, n)
        
    return None

if __name__ == '__main__':
    func()

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-

def dfs(num, dem, k, cur_num, prd, p, q, a, n):

    #print num, dem, k, cur_num, prd
    #time.sleep(0.5)
    if num == 0:
        #print "result: " + str(result)
        return 1

    result = 0


    while prd * i <= a:
        #print i, num, dem, k, cur_num, prd
        if (n - k) * dem < num * i:
            break
        # if num * i < dem:
        #     i += 1
        #     continue

        result += dfs((num * i) - dem, dem * i, k + 1, i, prd * i, p, q, a, n)
        i += 1

    return result

def func():
    while True:

        p, q, a, n = map(int, raw_input().split())

        if p == 0 and q == 0 and a == 0 and n == 0:
            break

        print dfs(p, q, 0, 1, 1, p, q, a, n)
        
    return None

if __name__ == '__main__':
    func()

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-

def dfs(num, dem, k, cur_num, prd, p, q, a, n):

    #print num, dem, k, cur_num, prd
    #time.sleep(0.5)
    if num == 0:
        #print "result: " + str(result)
        return 1

    result = 0

    i = cur_num
    while prd * i <= a:
        #print i, num, dem, k, cur_num, prd
        if (n - k) * dem < num * i:
            break
        # if num * i < dem:
        #     i += 1
        #     continue

        result += dfs((num * i) - dem, dem * i, k + 1, i, prd * i, p, q, a, n)
        i += 1

    return result

def func():
    while True:

        p, q, a, n = map(int, raw_input().split())

        if p == 0 and q == 0 and a == 0 and n == 0:
            break

        print dfs(p, q, 0, 1, 1, p, q, a, n)
        
    return None

if __name__ == '__main__':
    func()