オイラーのファイ関数とその別種について
まえがき
ACPC 2021 day2 E で出たオイラーのファイ関数に似た何かについてまとめました。
既出ではない...?（知らないだけかも）
本題
オイラーのファイ関数は 1 から N までの自然数について N と互いに素なものの個数を求めるものです。
ここに X を追加して X から N までの自然数について X と互いに素なものの個数を求めるものが今回の本題です。
求め方
オイラーのφ関数は公式が存在し、
$ \phi(n) = n \displaystyle \prod_{i=1}^k \left(1- \dfrac{1}{p_i} \right )ϕ(n)=n $
を計算することによって求められます。
お気持ちとしては素因数の倍数の個数を引いていっているだけです。
C++ で書くと以下のようになります。
計算量は $ O (\sqrt N ) $ です。
long long euler_phi(long long n) { long long res = n; for ( long long i = 2; i * i <= n; i++ ) { if ( n % i == 0 ) { res -= res / i; while ( n % i == 0 ) n /= i; } } if ( n > 1 ) res -= res / n; return res; }
別種の方
次に、先ほどの X から N までの自然数について X と互いに素なものの個数を求めていきます。
基本方針としては、X から N までの X - N + 1 個の中から X の素因数の倍数の個数を引いていく形です。（ X と互いに素ということは X のどの素因数の倍数でもない）
最初に、X と X が互いに素となるのは X が 1 のときだけなので、 X + 1 から N までの X - N 個の中から選ぶようにします。
とりあえず、X を素因数分解し、 $ p^{e_1} _ {1}, p^{e_2} _ {2}, ... , p^{e_k} _ {k} $ と k 個の素因数に分解できたとします。
これら k 個の素因数 $ p _ {1} , p _ {2} , ... , p _ {k} $ について、
- 1 種類選んで掛け合わせた数の N - X 個の中にある倍数の個数 （ $ _ k \mathrm{C}_1 $ 個存在する ）
- 2 種類選んで掛け合わせた数の N - X 個の中にある倍数の個数 （ $ _ k \mathrm{C}_2 $ 個存在する ）
︙
- k 種類選んで掛け合わせた数の N - X 個の中にある倍数の個数 （ $ _ k \mathrm{C}_k $ 個存在する ）
について見ていきます。
例として、X = 6, N = 12 の場合を見ていきます。
7, 8, 9, 10, 11, 12 の 6 個が対象の範囲です。
6 = 2 $ \times $ 3
と素因数分解して、
2 の倍数である 8, 10, 12 の 3 つを削ります。
3 の倍数である 9, 12 の 2 つを削ります。
ここで、 2 の倍数でもあり 3 の倍数でもある（ 6 の倍数 ） 12 を削りすぎてしまったので
6 の倍数である 12 の 1 つを足します。
そうすると、式としては以下のようになります。
$ \frac{12-6}{2} + \frac{12-6}{3} + \frac{12-6}{6} $
このように、素因数を奇数個使う場合は引き、偶数個使う場合は足すというような包除原理をして求めることができます。
1 から k 種類選んで掛け合わせた数というのは
$ \displaystyle \sum_{i=1}^{k} {} _ {k} C _ { i } = 2 ^ {k} $
通りあるので、素因数使う使わないの bit 全探索をして足し引きしていけば求められます。
よって、計算量が $ O( \sqrt{X} 2 ^ {k} ) $ 程度となり求めることができました。
以下、実装例です。
long long alternative_euler_phi(long long x, long long n) { if ( x == 1 ) return n; auto ps = prime_factor(x); ps.erase(unique(ps.begin(), ps.end()), ps.end()); int k = ps.size(); long long res = n - x; for ( int i = 1; i < (1 << k); i++ ) { long long prod = 1; int cnt = 0; for ( int j = 0; j < k; j++ ) { if ( i >> j & 1 ) { prod *= ps[j]; cnt++; } } if ( cnt % 2 ) { res += (n - x) / prod; } else { res -= (n - x) / prod; } } return res; }
おまけ
N を固定して X が 1 から N まであるテーブルとして求める場合は愚直に $ O(N \sqrt{N} 2 ^ {k} ) $ とするよりも高速にすることができます。
事前に 1 から N までの平方因子を持たない数についての素因数の個数を求めておきます。
そうすると平方因子を持たない整数側（ある数 X の約数）から包除原理をしていくことができ、計算量が $ O(N \log N ) $ 程度になります。
