2008-12-06から1日間の記事一覧
オイラー関数のメモ化まずはメモ化しない愚直なコード # euler.py def gcd(x, y): while y != 0: x,y = y,x%y return x def euler(n): if n==1: return 1 cnt = 0 for i in xrange(1, n): if gcd(n, i) == 1: cnt += 1 return cnt def main(): for n in xran…
オイラー関数のメモ化まずはメモ化しない愚直なコード # euler.py def gcd(x, y): while y != 0: x,y = y,x%y return x def euler(n): if n==1: return 1 cnt = 0 for i in xrange(1, n): if gcd(n, i) == 1: cnt += 1 return cnt def main(): for n in xran…