【筆記】Euler function 歐拉函數

  • 歐拉函數 Phi(x):找出「小於 x」 的「正整數」中「與 x 互質」的數的數目。
  • 【實作】找出小於 10 的正整數中與 10 互質的數的數目。(參考下圖)
    • 在 [2, sqrt(x)] 區間內,每找到一個 x 的質因數 p,便把 ret (初始值為 x) 乘上 (p-1) / p。(或是 ret -= ret / p)
    • 例如,10 有 2 和 5 兩個質因數,10 * (2 – 1) / 2 = 5,5 * (5 – 1) / 5 = 4。
    • 「小於 10」且「與 10 互質」的數的數目有 4 個:1, 3, 7, 9。
  • 【範例】T2498 [SDOI2012] Longge的问题
int Phi(int x){
    // 歐拉函數Phi(x)
    //「小於 x」 的「正整數」中「與 x 互質」的數的數目
    if (x < 2) return 0;
    int ret = x;
    int sq = sqrt(x);
    for (int p=2; p<=sq; p++){
        if (x % p == 0){
            while (x % p == 0) x /= p;
            ret -= ret / p;
        }
        if (x == 1) break;
    }
    if (x > 1) ret -= ret / x;
    return ret;
}
分享本文 Share with friends