オイラーのトーシェント関数についての話です。
きっかけは、AIZU ONNLINE JUDGEの整数論(NTL)からの"Euler's Phi Function"の出題でした。
https://onlinejudge.u-aizu.ac.jp/problems/NTL_1_D
オイラーのトーシェント関数とは、Wikipediaによれば...
>正の整数 n に対して、 n と互いに素である 1 以上 n 以下の自然数の個数 φ(n) を与える数論的関数 φ である。
（ここで (m, n) は m と n の最大公約数を表す）
>慣例的にギリシャ文字のφで表記されるため、オイラーのφ関数（ファイかんすう、phi function）とも呼ばれる。
>また、簡略的にオイラーの関数と呼ぶこともある。
ja.wikipedia.org
>例えば、1, 2, 3, 4, 5, 6 のうち 6 と互いに素なのは 1, 5 の 2 個であるから、定義によれば φ(6) = 2 である。
>また例えば 1, 2, 3, 4, 5, 6, 7 のうち 7 以外は全て 7 と互いに素だから、φ(7) = 6 と定まる。
>なおトーシェント関数の値域に含まれない自然数をノントーシェントという。
そういえば、φ(ファイ)って、参考書とか問題集によっては、空集合を表すのに使われるけれど、それは代用記号であって、全然違います。
だから、空集合Øは空集合であって、オイラーのφ関数はオイラーのトーシェント関数です。
そして、AIZU ONNLINE JUDGEの整数論(NTL)からの"Euler's Phi Function"の出題では...
「正の整数 n について、1 から n までの自然数のうち n と互いに素なものの個数を求めよ」
はい、こんなレベルだったら、もうパっと見て秒で解けるけれど...
最近思い知らされているのが、「僕は知らないことが多すぎる」ってことで、何かを1つ知ると、そこから知らない何かがブワーって出てきて...えーっと、『進撃の巨人』みたいなイメージです。
数学で言うと、オイラーだけではなくて、巨人が多すぎるし、僕はどこへも行けないのではないだろうかって、まぁ、要するに落ち込みます。
競技プログラミングで言うと、やっている人には伝わると思うけれど、「レーティング」とか、ね。
「レーティング」とか、ね。
はい、大事なことなので二回言いました。
まぁ、まぁ、まぁ...やるしかないからやります。
僕が作成、提出したコードは、以下のとおりです。
Aizu Online Judge in C++ #NTL_1_D : Euler's Phi Function
/* Aizu Online Judge in C++ #NTL_1_D : Euler's Phi Function https://onlinejudge.u-aizu.ac.jp/problems/NTL_1_D 提出コードの解答例 https://neguse-atama.hatenablog.com */ #include<bits/stdc++.h> using namespace std; long long phi(long long n){ long long r=n; for(long long i=2;i<=sqrt(n);i++){ if(n%i==0){ r-=(r/i); while(n%i==0){ n/=i; } } } if(n>1){ r-=(r/n); } return r; } int main(void){ long long n; cin>>n; cout<<phi(n)<<endl; return 0; }
それから、ついでに『完全トーシェント数』について...
完全トーティエント数 - Wikipedia
>完全トーシェント数は、自然数のうち、以下の等式を満たす数 n である。
>ここで φ はオイラーのトーシェント関数である。
>一般に完全トーシェント数 n は以下の式を満たす。
>完全トーシェント数は無数にあり、そのうち最小の数は 3 である。
>ほとんどの完全トーシェント数は 3 の倍数であり、3 の倍数でない完全トーシェント数のうち最小の数は 4375 である。
>特に 3 の累乗数 (3, 9, 27, 81, 243, 729, 2187, …) は全て完全トーシェント数である。
ね、1つクリアすると、また知らなかったのが出てくるぅー、はい、落ち込めるわー。
いや、やるけれどね。
設問の出典は、プログラミング問題のオンライン採点システム「Aizu Online Judge（AOJ）」です。
http://judge.u-aizu.ac.jp/onlinejudge/
