誕生日のパラドックス

範囲 N の乱数列の重複探索は基本的に計算量 O(√N) で終了する。 from random import randrange n = 10**9+7 s = set() while True: x = randrange(n) if x in s: break s.add(x) print(len(s)) O(√N) 個以内に重複が見つかる理由は誕生日のパラドックスで、重複の判定にハッシュテーブルを使ってるので全体計算量も O(√N) 。 ポラードのρ法は N の約数(真の約数)の探索を、範囲 N の乱数列の重複探索で行うアルゴリズム。 乱数列から選んだ x, y が GCD(|x-y|,…

第2話「ようこそ、野クルヘ」5人いっしょにはならんのね 各務原なでしこ 名字の読み方が判明した。かがみはら。同名の地名が由来の名字らしい。これまでに会ったことも聞いたこともない。 野クル タイトルの野クルは、野外活動サークルの略。 メガネパッツンツインテールの大垣千明と、おっとり関西弁お姉さんの犬山あおいが結成したサークル。部室が超狭く、四人以上部員を集めて部に昇格することを目論んでいる。 犬山は狭いからか、棚に腰掛けて座っていた。それでも二人が大きく動くと、お互いの体がぶつかっていた。大垣曰く活動は外だから問題ないとのこと。 狭いとはいえ、二人でサークルを発足でき、部室を与えられ、校内で火器…