寝癖頭の解法

小学生の目線から、勉強中の覚え書きを投稿、更新していきます。

オイラーのトーシェント関数について

オイラーのトーシェント関数についての話です。
きっかけは、AIZU ONNLINE JUDGEの整数論(NTL)からの"Euler's Phi Function"の出題でした。
https://onlinejudge.u-aizu.ac.jp/problems/NTL_1_D

オイラーのトーシェント関数とは、Wikipediaによれば...
>正の整数 n に対して、 n と互いに素である 1 以上 n 以下の自然数の個数 φ(n) を与える数論的関数 φ である。
f:id:neguse_atama:20210923120420p:plain
(ここで (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 である。
f:id:neguse_atama:20210923143942p:plain
>ここで φ はオイラーのトーシェント関数である。

>一般に完全トーシェント数 n は以下の式を満たす。
f:id:neguse_atama:20210923143959p:plain
>完全トーシェント数は無数にあり、そのうち最小の数は 3 である。
>ほとんどの完全トーシェント数は 3 の倍数であり、3 の倍数でない完全トーシェント数のうち最小の数は 4375 である。
>特に 3 の累乗数 (3, 9, 27, 81, 243, 729, 2187, …) は全て完全トーシェント数である。
ね、1つクリアすると、また知らなかったのが出てくるぅー、はい、落ち込めるわー。
いや、やるけれどね。

設問の出典は、プログラミング問題のオンライン採点システム「Aizu Online Judge(AOJ)」です。
http://judge.u-aizu.ac.jp/onlinejudge/