欧拉函数

定义

欧拉函数$\varphi(n)$表示, 对于正整数 $n$, 小于 $n$ 且和 $n$ 所互质正整数(包括 $1$)个数

$\varphi(n)= n\prod (1-\frac{1}{p_i}), $ $p_i$为 $n$ 所有质因数, $n$ $\neq 0$

$\varphi(1) = 1$, 唯一和 1 互质数就是 1 本身

证明

对于 $n$ 一个质因数$p_i$

$p_i$ 在 $n$ 以内$p_i$为倍数均匀分布

对于质因数$p_i$

$n$ 以内有$\frac{1}{p_i}$个数是$p_i$的倍数, 有$1 - \frac{1}{p_i}$个数不是$p_i$的倍数

对于质因数$p_j$

有$1 - \frac{1}{p_j}$个数不是$p_j$的倍数, 则有$(1 - \frac{1} {p_i})(1 - \frac{1}{p_j})$个数即不是$p_i$也不是$p_j$的倍数

… 最终有$n\prod (1-\frac{1}{p_i})$个数与 $n$ 互质

示例

$\varphi(10) = 10(1 - \frac{1}{2})(1 - \frac{1}{5} ) = 4$ $(1, 3, 7, 9)$

$\varphi(30) = 30(1 - \frac{1}{2})(1 - \frac{1}{3} )(1 - \frac{1}{5} ) = 8$

$\varphi(49)= 49(1 - \frac{1}{7} ) = 42$

获取

单个数

#include <iostream>

typedef long long ll;

ll GetEular(const ll n){
    ll ans = n;
    for(int i = 2; i * i <= n; i++){
        if(n % i == 0){
            // 对应欧拉函数通式即 ans = ans(1 - 1 / i)
            ans  = ans / i * (i - 1);
            // 为保证完全消除刚才得到的 i 因子
            // 确保下一个得到的 i 是 n 的素因子
            while(n % i == 0){
                n /= i;
            }
        }
    }
    // 为保证已经除完了 n 的所有的素因子
    // 因为有可能还会出现一个未除的因子, 若结尾出现 n>1, 说明还剩一个素因子未除
    if(n > 1){
        ans = ans / n * (n - 1);
    }
    return ans;
}

打表法

const int maxn = 1000;

int p[maxn];

p[1] = 1;

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

性质

若 $p$ 是素数

$\varphi(p) = p-1$

对于任意两个素数 $p$、$q$

存在$\varphi( pq ) = pq - 1$

对于正整数 $n$, 若 $n = p_1^{q_1} + p_2^{q_2} + \cdots + p_n^{q_n}$且$p_1p_2\cdots p_n$ 为 $n$ 的所有素因子

则$\varphi(n) = n(1 - \frac{1}{p_1})(1 - \frac{1}{p_2})\cdots(1 - \frac{1}{p_n})$

若$n = p^k$ ($p$ 为质数)

则$\varphi(n) = (p-1)p^{k-1}$

小于 $n$ 且与 $n$ 互质的数的和

$S = n \times \frac{\varphi(n)}{2}$

欧拉降幂

欧拉定理

若$m, n互质, n^{\varphi(m)} ≡ 1 (mod$ $m)$

#include<iostream>
#include<cstring>
#include<cmath>

typedef long long ll;
const int MaxN=1000100;

ll FastPow(ll  a,ll b,ll mod) {
    ll ans=1;
    a %= mod;
    while(b) {
        if(b&1) {
            ans = (ans*a)%mod;
        }
        b >>= 1;
        a = (a*a)%mod;
    }
    return ans;
}

ll GetEular(ll x) {  //欧拉函数
    ll n = x;
    for(ll i = 2; i*i <= x; i++) {
        if(x % i == 0) {
            n = n / i * (i-1);
            while(x % i == 0) {
                x /= i;
            }
        }
    }
    if(x > 1) {
        n = n / x * (x-1);
    }
    return n;
}

ll EulerDropPow(ll a,char b[],ll c) {  
    ll num = GetEular(c);  //c的欧拉函数值
    ll pows = 0;  //存储降了之后的幂
    for(ll i = 0,len = strlen(b); i<len; ++i) {
        pows = (pows*10+b[i]-'0') % num;
    }
    //b mod &(c) + &(c) 
    pows += num;
    return fastPow(a,pows,c); //快速幂
}

上篇快速幂

下篇sql使用