オイラーのトーシェント関数
オイラーのトーシェント関数は、以下の形で表すことができます(正確な定義は オイラーのφ関数 - Wikipedia にあります)。
この式の括弧内の分母を揃えます。
プログラムで値を得るときは、この式を元に以下のように計算していました。
import std.experimental.all; int totient(int n) { int ret = n; for (int p = 2; p * p <= n; p++) { if (n % p == 0) { ret = ret / p * (p - 1); while (n % p == 0) n /= p; } } if (n != 1) ret = ret / n * (n - 1); return ret; } void main() { writeln(iota(1, 20).map!totient); //=> [1, 1, 2, 2, 4, 2, 6, 4, 6, 4, 10, 4, 12, 6, 8, 8, 16, 6, 18] }
npca2013年部誌_競技プログラミングと初等整数論入門(PDF) と読むと、 この関数を次のように計算していました。
int totient2(int n) { int ret = n; for (int p = 2; p * p <= n; p++) { if (n % p == 0) { ret -= ret / p; // ここが違う while (n % p == 0) n /= p; } } if (n != 1) ret -= ret / n; // ここが違う return ret; }
こちらのほうが計算が単純になっていますね。この計算方法がどこから来るのか考えてみます。
最初の式に戻りますと、
この式の最初の と を掛けると
となります。最初の括弧内の項では、 から を引いています。 次に最初の括弧内の項を と置くと
となり、 を展開すると
となります。ここで行っているのは、 から を引いています。
つまり、これは ret -= ret / p
がやっていることなのですね。