habara-k / ICPCLibrary

https://habara-k.github.io/ICPCLibrary/
3 stars 0 forks source link

φ関数を追加 #12

Closed kanra824 closed 3 years ago

kanra824 commented 4 years ago

φ(n) = nと互いに素な1以上n以下の整数の個数 O(sqrt(n))

habara-k commented 3 years ago

@kanra824 p1, ..., pk をnの素因数としたとき、 n (1 - 1/p1) ... (1 - 1/pk) でもとまる(感覚としては各素因数piを約数に持つ確率が1/pi で独立。それを全部潜り抜ける確率 n個がφ(n)に他ならない)

覚えやすいしそこまで必要はなさそう

habara-k commented 3 years ago

https://github.com/habara-k/ICPCLibrary/pull/47 で追加した