【基礎数論】10分でオラ関数の計算を学ぶ

オーラ関数
読者の皆様のご指摘を歓迎します.ありがとうございます.
まず、オラ関数は何なのかを知る必要があります.
くだらないことを言わない~オーラ関数とは、正の整数nに対して、nより小さく、nと互いに質のある正の整数(1を含む)の個数について、φ(n) .
オーラ関数の一般式:φ(n)=n*(1-1/p1)*(1-1/p2)*(1-1/p3)*(1-1/p4)…..(1−1/pn)p 1,p 2......pnはnのすべての素因数であり、nは0でない整数である.φ(1)=1(一意と1の互質の数は1そのものである).
上記の一般式は、オラ関数を計算する最も重要なステップであるため、心に刻まなければならない.覚えておいて~~~~
はい、最も簡単で、一般式によって最も簡単なコードを得ることができます.

int euler(int n)  
{  
    int ans=n;  
    for(int i=2;i*i<=n;i++){  
        if(n%i==0){  
            ans-=ans/i;  
            while(n%i==0){  
                n/=i;  
            }  
        }  
    }  
    if(n>1)ans-=ans/n;  
    return ans;  
}

難解な1:コードの中のans-=ans/i;この一歩がオーラ関数に対応する一般式なのか、それとも分かりやすいのか.
難解2:while(n%i==0)n/=i;この文は、私たちがさっき得たi因子を完全に除去することを保証するためです.次に得られるiがnの素因子であることを確認した.
難解な3:if(n>1)ans-=ans/n;この文は、nのすべての素因子を除去したことを保証するために、私たちが除去していない因子が現れる可能性があります.もし最後にn>1が現れたら、私たちはまだ素因子木が1つ残っていることを示しています.
上记のコードのを理解するのは练习することができます~推荐テーマ:HDOJ 1787题解:クリックしてリンクを开けます
しかし、私达の普通の问题はもちろんこんなに简単ではありません~~少し难しいです...
もし私たちが要求する数が多いならば、1つ1つ求めれば簡単にタイムアウトするので、私たちは自然に時計を打つことを考えます.
もし私たちが上記の考えに基づいて、最も素朴な時計を打つならば.

void euler()
{
    p[1]=1;
    for(int i=2;i<=MAXN;i++){
        int n=i;
        p[i]=i;
        for(int j=2;j*j<=n;j++){
            if(n%j==0){
                p[i]=p[i]/j*(j-1);
                while(n%j==0) n=n/j;
            }
        }
        if(n>1) p[i]=p[i]/n*(n-1);
    }
    for(int i=2;i<MAXN;i++)
        p[i]+=p[i-1];
}

この時計の打ち方はあまり理想的ではありません...
次の2つの比較的速い時計の打ち方をお勧めします.
ps:これは少し早いようですね~

void euler()  
{  
    E[1]=1;  
    for(int i=2;i<maxn;i++)  
        E[i]=i;  
    for(int i=2;i<maxn;i++){  
        if(E[i]==i)  
        for(int j=i;j<maxn;j+=i){  
            E[j]=E[j]/i*(i-1);  
        }  
    }  
}

2つ目:

void euler()  
{  
    for(int i=2;i<maxn;i++){  
        if(!E[i])  
        for(int j=i;j<maxn;j+=i){  
            if(!E[j])E[j]=j;  
            E[j]=E[j]/i*(i-1);  
        }  
    }  
}

上記の打表方法の考え方は最初とはあまり違いません.しかし、最適化されているので、比較的速いです.
次のように分析します.
まず,ここで列挙したのは素因子である.素因子が少ないので、素因子を列挙すると複雑さが大幅に最適化されるに違いありません.
では、私たちが得たものが必ず素因子であることをどのように保証しますか?これがif文の役割です.例えば、第1の方法では、第2のforサイクルでは、すべての数を素因子で割っています.このようにして得られる複雑さは、各数を列挙し、素因子(最初の打表法)を探す打表よりも最適化されるに違いない.
推荐题目:HDOJ 2824问题解:クリックしてリンクを开けます
普段、私たちは問題をして、普通は直接あるいはただ1つの数のEuler関数の値を考察しません.いくつかの変形、あるいはオーラ関数のいくつかの性質です.
ここで私はいくつかのオーラ関数でよく使われる性質をまとめ、読者にもっと補充してほしい.
Euler関数の性質(継続的な更新):
1 N>1であり、Nより大きくなく、N相互素とのすべての正の整数の和は1/2*M*eular(N)である.推荐题目:HDOJ 3501问题解:クリックしてリンクを开けます
②(N%a=0&&(N/a)%a=0)の場合、E(N)=E(N/a)*a;(N%a==0&&(N/a)%a!=0)は、E(N)=E(N/a)*(a-1);