歐拉函數模闆

歐拉函數:

定義：用于計算 p(n)，比n小的所有與n互質的數。

計算公式：p(n)=n*(1-1/p1)*(1-1/p2)....*(1-1/pk)【p1,p2,pk都是n的素因子】

另：若n=p1^q1*p2^q2*.....*pk^qk

則，p(n)=(p1-1)*p1^(q1-1)*(p1-1)*p2^(q2-1)......*(pk-1)*pk^(qk-1)

性質：若m,n互質，φ(mn)=φ(m)φ(n)。當n為奇數時，φ(2n)=φ(n)

歐拉定理：

a,m互質，a^φ(m)≡1(mod m)

例：2,3互質，那麼，2^2%3=1

推論：對于互質的數a、n，滿足a^(φ(n)+1) ≡ a (mod n)

 歐拉公式的延伸：小于n 與n互質的數的和 是euler(n)*n/2

求歐拉函數的模闆：

int euler(int n)//傳回euler(n)
{
     int i;
     int res = n,a = n;
     for(i = 2;i*i <= a; ++i)
     {
         if(a%i == 0)
         {
             res -= res/i; //p(n) = (p - p/p1)(1 - 1/p2)......
             while(a%i == 0) a/=i;
         }
     }
     if(a > 1) res -= res/a;//存在大于sqrt(a)的質因子
     return res;
}
      

void SE()//select euler//類似于素數篩選法
{
    int i,j;
    euler[1] = 1;
    for(i = 2;i < Max; ++i)  euler[i]=i;
    for(i = 2;i < Max; ++i)
    {
         if(euler[i] == i)//這裡出現的肯定是素數
         {
           for(j = i; j < Max; j += i)//然後更新含有它的數
           {
              euler[j] = euler[j]/i*(i - 1); // n*(1 - 1/p1)....*(1 - 1/pk).先除後乘
           }
        }
    }
     //for (int i = 1; i <= 20; ++i) printf("%d ",euler[i]);
}