Problem:


Unable Count

  
I would, if I could,

  If I couldn't how could I?

  I couldn't, without I could, could I?

  Could you, without you could, could ye?

  Could ye? could ye?

  Could you, without you could, could ye?

It is true, as this old rhyme says, that we can only DO what
we can DO and we cannot DO what we cannot DO. Changing some of
DOs with COUNTs, we have another statement that we can only COUNT
what we can DO and we cannot COUNT what we cannot DO, which looks
rather false. We could count what we could do as well as we could
count what we couldn't do.  Couldn't we, if we confine ourselves
to finite issues?

Surely we can count, in principle, both what we can do and
what we cannot do, if the object space is finite. Yet, sometimes
we cannot count in practice what we can do or what we cannot do.
Here, you are challenged, in a set of all positive integers up
to (and including) a given bound n, to count
all the integers that cannot be represented by a formula of
the form a*i+b*j, where a and
b are given positive integers and i and j
are variables ranging over non-negative integers. You are requested
to report only the result of the count, i.e. how many integers
are not representable.
For example, given n = 7, a = 2, b = 5,
you should answer 2, since 1 and 3 cannot be represented in a
specified form, and the other five numbers are representable as follows:

   2 = 2*1 + 5*0,    4 = 2*2 + 5*0,    5 = 2*0 + 5*1,
   6 = 2*3 + 5*0,    7 = 2*1 + 5*1.

Input

The input is a sequence of lines. Each line consists of three integers,
n, a and b, in this order, separated by a
space. The integers n, a and b are
all positive and at most one million, except those in the last
line. The last line consists of three zeros.

Output

For each input line except the last one, your program should
write out a line that contains only the result of the count.

Sample Input

10 2 3
10 2 5
100 5 25
0 0 0

Output for the Sample Input

1
2
80



Sample input:
10 2 3
10 2 5
100 5 25
0 0 0


Sample output:
1
2
80

Submission status: Wrong Answer

Solution code:
while True:
    n, a, b = map(int, input().split())
    if not n:
        break
    dp = [False] * (n + abs(a - b))
    dp[1:n + 1] = [True] * n
    for i in range(n - min(a, b)):
        if not dp[i]:
            dp[i + a] = False
            dp[i + b] = False
    print(dp.count(True))

Submission status: Time Limit Exceeded

Solution code:
# AOJ 1105: Unable Count
# Python3 2018.7.14 bal4u

while True:
	n, a, b = map(int, input().split())
	if n == 0: break
	f = [0]*(n<<1)
	for x in range(0, n, a):
		for y in range(0, n+1, b): f[x+y] = 1
	print(n-sum(f[1:n+1]))

Submission status: Time Limit Exceeded

Solution code:
def getlcm(a,b):
    aa=a
    bb=b
    while aa!=0:
        [aa,bb]=[bb%aa,aa]
    return a*b/bb

while(1):
    [n,a,b]=[int(x) for x in raw_input().split()]
    if n==0:
        break
    else:
        [a,b]=[min(a,b),max(a,b)]
        LCM=getlcm(a,b)
        able=[]
        for i in range(LCM/a):
            for j in range(n):
                if a*i+b*j>=n:
                    break
                able.append(a*i+b*j)
        ans=n-len(able)
        print ans

Submission status: Time Limit Exceeded

Solution code:
while True:
    n,a,b=map(int,raw_input().split())
    if n==a==b==0:break
    L=[False]*(n+1)
    for i in range(n/a+1):
        for j in range(n/b+1):
            t=i*a+j*b
            if t<=n:
                L[t]=True
    print L.count(False)

Submission status: Time Limit Exceeded

Solution code:
while True:
    n,a,b=map(int,raw_input().split())
    if n==a==b==0:break
    count=n
    for i in range(1,n+1):
        x=i
        while x>=0:
            if x%a==0:
                count-=1
                break
            x-=b
    print count

Submission status: Memory Limit Exceeded

Solution code:
while 1:
	n,a,b = map(int,raw_input().split())
	if n == 0: break
	ans = set([a*i+b*j for i in range(n/a+1) for j in range((n-a*i)/b+1)])
	print n - len(ans) + 1

Submission status: Accepted

Solution code:
# AOJ 1105: Unable Count
# Python3 2018.7.14 bal4u

while True:
	n, a, b = map(int, input().split())
	if n == 0: break
	f = [0]*(n+max(a,b)+1)
	f[0], f[a], f[b] = 1, 1, 1
	s = min(a, b)
	for k in range(s, n+1):
		if f[k]: f[a+k] = 1; f[b+k] = 1
	print(n-sum(f[s:n+1]))

Submission status: Accepted

Solution code:
def getlcm(a,b):
    aa=a
    bb=b
    while aa!=0:
        [aa,bb]=[bb%aa,aa]
    return a*b/bb

while(1):
    [n,a,b]=[int(x) for x in raw_input().split()]
    if n==0:
        break
    else:
        [a,b]=[min(a,b),max(a,b)]
        LCM=getlcm(a,b)
        #able=[]
        able=-1
        for i in range(LCM/a):
            for j in range((n-a*i)/b+1):
                able+=1
        ans=n-able
        print ans

Submission status: Accepted

Solution code:
while 1:
    n,a,b=map(int,input().split())
    if n==a==b==0:break
    c=0;d=[1]+[0]*1000000
    for i in range(0,n+1):
        if d[i]:
            if i+a<=n:d[i+a]=1
            if i+b<=n:d[i+b]=1
        else:c+=1
    print(c)

Submission status: Accepted

Solution code:
while 1:
    n,a,b=map(int,input().split())
    if n==a==b==0:break
    c=0;d=[1]+[0]*2000000
    for i in range(0,n+1):
        if d[i]:d[i+a]=d[i+b]=1
        else:c+=1
    print(c)

Submission status: Accepted

Solution code:
while 1:
    n,a,b=map(int,input().split())
    if n==a==b==0:break
    c=0;d=[1]*(n+1)
    for x in range(a):
        for i in range(x*b,n+1,a):d[i]=0
    print(sum(d))

Submission status: Accepted

Solution code:
while 1:
    n,a,b=map(int,input().split())
    if n==0:break
    d=[1]*(n+1)
    for x in range(a):
        for i in range(x*b,n+1,a):d[i]=0
    print(sum(d))

Submission status: Accepted

Solution code:
while True:
    n, a, b = map(int, input().split())
    if not n:
        break
    if a > b:
        a, b = b, a
    dp = [False] * (n + b - a + 1)
    dp[1:n + 1] = [True] * n
    for i in range(n - a + 1):
        if not dp[i]:
            dp[i + a] = False
            dp[i + b] = False
    print(dp.count(True))

Submission status: Accepted

Solution code:
while True:
    n,a,b = map(int, input().split())
    if n==0: break
    ok = [1]*(n+1)
    for i in range(b):
        for j in range(0,n-i*a+1,b):
            ok[i*a+j] = 0
    print(sum(ok))

Submission status: Accepted

Solution code:
while True:
    n,a,b=map(int,raw_input().split())
    if n==a==b==0:break
    L=[True]*(n+1)
    for i in range(a):
        x=b*i
        if x>n:break
        while x<=n:
            L[x]=False
            x+=a
    print L.count(True)

Submission status: Accepted

Solution code:
while 1:
	n,a,b = map(int,raw_input().split())
	if n == 0: break
	dp = [0]*(n+1)
	if a < n+1: dp[a] = 1
	if b < n+1: dp[b] = 1
	for i in range(n+1):
		if dp[i]:
			if i+a < n+1: dp[i+a] = 1
			if i+b < n+1: dp[i+b] = 1
	print n - sum(dp)

Submission status: Accepted

Solution code:
while 1:
	n,a,b = map(int,raw_input().split())
	if n == 0: break
	dp = [0]*(n+max(a,b)+1)
	dp[a] = dp[b] = 1
	for i in range(n+1):
		if dp[i]:
			dp[i+a] = dp[i+b] = 1
	print n - sum(dp[:n+1])

Submission status: Accepted

Solution code:
while 1:
	n,a,b = map(int,raw_input().split())
	if n == 0: break
	S = [1]*(n+1)
	for i in range(a):
		s = b*i
		while s <= n:
			S[s] = 0
			s += a
	print sum(S)

Submission status: Runtime Error

Solution code:
# AOJ 1105: Unable Count
# Python3 2018.7.14 bal4u

while True:
	n, a, b = map(int, input().split())
	if n == 0: break
	f = [0]*(n+1)
	for x in range(0, n, a):
		for y in range(0, n+1, b): f[x+y] = 1
	print(n-sum(f))

Submission status: Runtime Error

Solution code:
# AOJ 1105: Unable Count
# Python3 2018.7.14 bal4u

while True:
	n, a, b = map(int, input().split())
	if n == 0: break
	f = [0]*(n>>1)
	for x in range(0, n, a):
		for y in range(0, n+1, b): f[x+y] = 1
	print(n-sum(f[1:n+1]))

Submission status: Runtime Error

Solution code:
while 1:
	n,a,b = map(int,raw_input().split())
	if n == 0: break
	dp = [0]*(n+1)
	dp[a] = dp[b] = 1
	for i in range(n+1):
		if dp[i] == 1:
			if i+a < n+1: dp[i+a] = 1
			if i+b < n+1: dp[i+b] = 1
	print n - sum(dp)

Submission status: Runtime Error

Solution code:
while 1:
	n,a,b = map(int,raw_input().split())
	if n == 0: break
	dp = [0]*(max(n,a,b)+1)
	dp[a] = dp[b] = 1
	for i in range(n+1-min(a,b)):
		if dp[i]:
			dp[i+a] = dp[i+b] = 1
	print n - sum(dp[:n+1])