mayoko’s diary

プロコンとかいろいろ。

Codeforces Round #328 (Div. 2) C. The Big Race

解法

まず, w と b の最小公倍数 lcm ごとになにか周期になっているっぽいことは明らかです。

で, この問題の場合は L が n * lcm + a (0 <= a <= min(w, b)-1, n は自然数) と表せる場合のみ結果が引き分けになります。ただ, n = 0, a = 0 の場合は問題の都合上除かれるのでその点は注意です。

def gcd(a, b):
    if (a > b):
        a, b = b, a

    if (a == 0):
        return b
    else:
        return gcd(b%a, a)

t, w, b = map(int, raw_input().split())

lcm = b*w / gcd(b, w)
mini = min(b, w)

cnt = 0
num = t/lcm
cnt += num*mini
tmp = t-lcm*num
cnt += min(tmp, mini-1)

g = gcd(t, cnt)
t /= g
cnt /= g
print u"%d/%d" % (cnt, t)