Codeforces Round #198 (Div. 2)

はい。
http://codeforces.com/contest/340

A. The Wall

ざっくりと大意

・Iahubはx-1飛ばしの箇所を赤く、Floydはy-1飛ばしの箇所をピンクにレンガに色を塗る。
・色を塗るa-bの区間で2人共が塗る対象になるのは何箇所か？？

方針のようなもの

・a-b間が最大で1-2*10⁹になることがあるらしいのでxずつ加算でループは時間が足りなくなる。
・2人共が塗る対象になるのは最小公倍数ごとに発生するのでそれを利用する。

x,y,a,b=map(int,raw_input().split())
ans=chk=0
x,y=max(x,y),min(x,y)


def gcd(a,b):
    while a%b:a,b=b,a%b
    return b

def lcm(a,b):
    return a*b/gcd(a,b)

chk=lcm(x,y)
ans=b/chk-a/chk
print ans if a%chk else ans+1