[AcWing]，数学知识(二)，证明推导欧拉函数，快速幂，扩展欧几里得算法

欧拉函数

欧拉公式

对于每一个数$N$，都可以分解为$N=p_1^{{\alpha }_1}\times p_2^{{\alpha }_2}\times \cdots \times p_k^{{\alpha }_k}$

其中，$p_1{p}_2\cdots p_k$为质数，${\alpha }_1{\alpha }_2\cdots {\alpha }_k$为对应的质数的出现次数

那么，最后的结果为$res=N\times \frac{p_1-1}{p_1}\times \frac{p_2-1}{p_2}\times \cdots \times \frac{p_k-1}{p_k}$

需要注意的一点

当我们在计算$N\times \frac{p_1-1}{p_1}$的时候，如果我们用$N\times (p_1-1)$，那么很容易发生溢出，所以我们采取先计算除法，在计算乘法

#include <iostream>
using namespace std;
int main() {
    int n;
    cin >> n;
    while (n --) {
        int x;
        cin >> x;
        int res = x;
        for(int i = 2; i <= x / i; i++)
            if(x % i == 0) {
                res = res /i * (i - 1) ;
                while(x % i == 0) x /= i;
            }
        if(x > 1) res = res / x * (x - 1);
        cout << res << endl;
    }
    return 0;
}

筛法求欧拉函数

思路：

①. i%primes[j] == 0，说明$primes[j]$是$i$的最小质因子，也是$i\times primes[j]$的最小质因子。所以说，只需要将一开始的基数修改为$primes[j]$即可

$res(i)=i\times \frac{p_1-1}{p_1}\times \frac{p_2-1}{p_2}\times \cdots \times \frac{p_k-1}{p_k}(i=p_k)$ i是一个质数

$\Rightarrow res(primes[j]\times i)=primes[j]\times i\times \frac{res(i)}{i}$

$\Rightarrow res(primes[j]\times i)=primes[j]\times res(i)$

② .i % primes[j] != 0，说明$primes[j]$不是$i$的因子，只是$i\times primes[j]$的最小质因子。因此，修改基数$1$为$primes[j]$后，还需要补上$primes[j]$这个质数的欧拉函数项

$res(i)=i\times \frac{p_1-1}{p_1}\times \frac{p_2-1}{p_2}\times \cdots \times \frac{p_k-1}{p_k}$

$\Rightarrow res(primes[j]\times i)=primes[j]\times i\times \frac{res(i)}{i}\times \frac{primes[j]-1}{primes[j]}$

$\Rightarrow res(primes[j]\times i)=res(i)\times (primes[j]-1)$

#include <iostream>
using namespace std;

typedef long long LL;
const int N =  1e6 + 10;
int primes[N],phi[N],cnt;
int vis[N];
int n;

void get_phi() {
    phi[1] = 1;
    for(int i = 2; i <= n; i++) {
        if(!vis[i]) {
            primes[cnt++] = i;
            phi[i] = i - 1;
        }
        
        for(int j = 0; primes[j] <= n / i; j ++) {
            vis[primes[j] * i] = 1;
            if(i % primes[j] == 0) {
                phi[primes[j] * i] = phi[i] * primes[j];
                break;
            }
            phi[primes[j] * i] = phi[i] * (primes[j] - 1);
        }
    }
}

int main() {
    cin >> n;
    get_phi();
    
    LL res;
    for(int i = 1; i <= n; i++) res += phi[i];
    cout << res << endl;
    return 0;
}

快速幂

快速幂

思路

1. 当指数$k$为$0$的时候，返回$1$
2. 当指数$k$为奇数的时候，返回$x\times x^{k-1}\times x^{k-1}$
3. 当指数$k$为偶数的时候，返回$x^{k/2}\times x^{k/2}$

• 递归

#include <iostream>

using namespace std;
typedef long long LL;
int n,a,b,c;

LL check(int k) {
    if(k == 0) return 1;
    if(k & 1) return check(k - 1) % c * a % c;
    LL x = check(k / 2);
    return (x * x) % c;
}

int main() {
    cin >> n;
    
    while(n --) {
        cin >> a >> b >> c;
        cout << check(b) << endl;
    }
    return 0;
}

• 递推

#include <iostream>

using namespace std;
typedef long long LL;
int n,a,b,c;

LL check() {
    LL res = 1;
    while(b) {
        if(b & 1) res = res * a % c;
        a = (LL) a * a % c;
        b >>= 1;
    }
    return res;
}

快速幂求逆元

当$n$为质数的情况

$a/b\equiv a\times x(\mathrm{m}\mathrm{o}\mathrm{d}n)$

同时$\times b$可以推导出$\Rightarrow a\equiv a\times b\times x(\mathrm{m}\mathrm{o}\mathrm{d}n)$
$\Rightarrow 1\equiv b\times x(\mathrm{m}\mathrm{o}\mathrm{d}n)$
$\Rightarrow b\times x\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}n)$

费马小定理: 如果p是一个质数，而整数a不是p的倍数，则有$a^{p-1}\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}p)$

由费马小定理可知，当$n$为质数时，$b^{n-1}\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}n)$
$\Rightarrow b\times b^{n-2}\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}n)$
所以说，当n为质数时，b的乘法逆元为$x=b^{n-2}(\mathrm{m}\mathrm{o}\mathrm{d}n)$

#include <iostream>

using namespace std;

typedef long long LL;
int n;

void check(int a,int b,int p) {
    LL res = 1;
    while(b) {
        if(b & 1) res = (res * a) % p;
        b >>= 1;
        a = ((LL)a * a) % p;
    }
    
    cout << res << endl;
}

int main() {
    cin >> n;
    while( n --) {
        int a,p;
        cin >> a >> p;
        if(a % p == 0) puts("impossible");
        else check(a,p-2,p);
    }
    return 0;
}

扩展欧几里得算法

当$n$不为质数时的情况

扩展欧几里得算法，用于求$ax+by=\gcd (a,b)$的解
$\Rightarrow exgcd(a,b,x,y)$

那么，当$b==0$的时候，$ax+by=a\Rightarrow ax+b\times 0=a$

$\Rightarrow ax=a$

$\Rightarrow x=1,y=0$

当$b!=0$的时候，$ax+by=\gcd (a,b)=\gcd (b,a\%b)$

$$\Rightarrow b{x}^{\prime }+(a\%b)y^{\prime }=\gcd (b,a\%b)$$

$$\Rightarrow b{x}^{\prime }+(a-\lfloor \frac{a}{b}\rfloor \times b)y^{\prime }=\gcd (b,a\%b)$$

$$\Rightarrow a{y}^{\prime }+b(x^{\prime }-\lfloor \frac{a}{b}\rfloor \times y^{\prime })=\gcd (b,a\%b)=\gcd (a,b)$$

所以说，可以得到的结果是$x=y^{\prime },y=x^{\prime }-\lfloor \frac{a}{b}\rfloor \times y^{\prime }$

#include <iostream>
using namespace std;
int n;

void ex(int a,int b,int& x,int& y) {
    if(!b) {
        x = 1, y = 0;
        return ;
    }
    int tx,ty;
    ex(b,a % b,tx,ty);
    x = ty, y = tx - a/b * ty;
}

int main() {
    cin >> n;
    while (n --) {
        int a,b,x,y;
        cin >> a >> b;
        
        ex(a,b,x,y);
        
        cout << x << " " << y << endl;
    }
    return 0;
}

线性同余方程

经过变化后可以得出：$a_i\times x_i-m_i\times y_i=b_i$
$$\Rightarrow a_i\times x_i+m_i\times y_i=b_i$$

所以说，就可以使用扩展欧几里得算法求出$x_i$的值，然后判断该等式方程是否存在解

该方程式存在解的充分必要条件是：$b$是$a$和$m$的最大公约数$d$的倍数

那么，我们最后使用扩展欧几里得算法所求出的结果$x$是基于$a$和$m$最大公约数的一个结果，想要求出和$b$相关的结果，需要将$x$扩大$b÷d$倍
$$x=x\times b÷d(\mathrm{m}\mathrm{o}\mathrm{d}m)$$

#include <iostream>
using namespace std;
int n;
typedef long long LL;

int ex(int a,int b,int& x,int& y) {
    if(!b) {
        x = 1, y = 0;
        return a;
    }
    int x1,y1;
    int ret = ex(b,a%b,x1,y1);
    x = y1;
    y = x1 - a / b * y1;
    return ret;
}

int main() {
    cin >> n;
    while(n --) {
        int a,b,m,x,y;
        cin >> a >> b >> m;
        int d = ex(a,m,x,y);
        if(b % d) puts("impossible");
        else {
            x = (LL)x * b / d % m;
            cout << x << endl;
        }
    }
}