歐拉函數(shù)φ(n)是1~n-1的與n互質(zhì)的數(shù)的個數(shù)

歐拉函數(shù)公式：φ(n)=n*(1-1/p1)*(1-1/p2)*(1-1/p3)*...*(1-1/pn)；這里的pi是n的所有質(zhì)因數(shù)，n>0。

歐拉定理：若n為素數(shù)，φ(n)=n-1。

若n的另一個素數(shù)p的a次冪，φ(p^a)=(p-1)*p^(a-1)，比p^a小的數(shù)有p^a-1個，那么有p^(a-1)-1個數(shù)能被p所整除(1~p^a-1中p的倍數(shù)一共p^(a-1)-1個)。φ(p)=p^a-1-(p^(a-1)-1)=(p-1)*p^(a-1)。

如果n為任意兩個數(shù)a和b的積，那么φ(a*b)=φ(a)*φ(b)

若n為奇數(shù)，則φ(2n)=φ(n);

我們可以把歐拉函數(shù)的通式改寫為:φ(n)=(n-n*p1)...(1-1/pn)，然后下面的歐拉函數(shù)的程序應(yīng)該就好理解了。

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

第一個找到的i一定是質(zhì)因數(shù)，while(n%i==0)n/=i;是完全消除i這個質(zhì)因子（參考n=(p1^a1)*(p2^a2)*……*(pk^ak) (為N的分解式)，pi是質(zhì)因子）。

還有素數(shù)表實現(xiàn)的代碼：

? ? 先把50 000以內(nèi)的素數(shù)用篩選法選出來并保存，以方便歐拉函數(shù)使用，這樣，在不考慮篩選法的時間復(fù)雜度，而單純看歐拉函數(shù)，其復(fù)雜度為O（x），x為O(√ˉn）以內(nèi)素數(shù)的個數(shù)。

bool boo[50000];
int p[20000];
void prim() {
    boo[0] = boo[1] = 1;
    int k = 0;
    for(int i = 2; i < 50000; i  ) {
        if(!boo[i])
            p[k  ] = i;
        for(int j = 0; j < k && i * p[j] < 50000; j  ) {
            boo[i * p[j]] = 1;
            if(!(i % p[j]))
                break;
        }
    }
}
int phi(int n) {
    int rea = n;
    for(int i = 0; p[i]*p[i] <= n; i  ) //對于一些不是素數(shù)的可不遍歷
        if(n % p[i] == 0) {
            rea = rea - rea / n;
            do
                n /= p[i];
            while(n % p[i] == 0);
        }
    if(n > 1)
        rea = rea - rea / n;
    return rea;
}

有時候我們遇見頻繁調(diào)用歐拉函數(shù)的題時，我們通常回預(yù)處理所有歐拉函數(shù)出來，用下面的遞推式。

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

另有一些題目中可能用的性質(zhì)? 轉(zhuǎn)自勱臻佳境

N>1，不大于N且和N互素的所有正整數(shù)的和是 1/2*M*eular(N)。

若(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);