単にその範囲の分数を列挙して分母分子が互いに素なものを数えるだけで1秒以内でした。
def gcd(n :Int, m :Int) :Int = if(m == 0) n else gcd(m, n % m) def count_reduced(d :Int) :Int = Iterator.range(d / 3 + 1, (d + 1) / 2).count(n => gcd(n, d) == 1) val N = 12000 println (Iterator.range(2, N + 1).map(count_reduced).sum)
