欧拉函数、欧拉、费马小定理、逆元、孙子定理

欧拉函数

$\phi(n)$表示小于等于n的数中与n互质的个数

$$\phi(n)=(p_{1}-1)p_{1}^{\alpha_{1}-1}*(p_{2}-1)p_{2}^{\alpha_{2}-1}*…*(p_{k}-1)p_{k}^{\alpha_{k}-1}=n*\Pi_{i=1}^{s}\frac{p_{i}-1}{p_{i}}$$

// C++ Version
int euler_phi(int n) {
  int ans = n;
  for (int i = 2; i * i <= n; i++)
    if (n % i == 0) {
      ans = ans / i * (i - 1);
      while (n % i == 0) n /= i;
    }
  if (n > 1) ans = ans / n * (n - 1);
  return ans;
}

• 欧拉函数是积性函数

• 当n为奇数，$\phi(n)=\phi(2n)$

• $n=\sum_{d|n}\phi(d)$

• if $n=p^{k}$,then $\phi(n)=p^k-p^{k-1}$

• 当n>2时，n是偶数

• n的因数的欧拉函数之和等于n

• 小于n的数中，与n互质的数的总和为：$\phi(n)$*n/2 (n>1)

筛法求欧拉函数

求$\phi(1),\phi(2)…,\phi(n)$

设$p_{1}$是n的最小质因子,$n'=\frac{n}{p_{1}}$

如果$n'modp_{1}=0$,$\phi(n)$=$p_{1}$*$\phi(n')$

如果$n'modp_{1}\neq0$,$\phi(n)$=$(p_{1}-1)$*$\phi(n')$

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

// C++ Version
void pre() {
  memset(is_prime, 1, sizeof(is_prime));
  int cnt = 0;
  is_prime[1] = 0;
  phi[1] = 1;
  for (int i = 2; i <= 5000000; i++) {
    if (is_prime[i]) {
      prime[++cnt] = i;
      phi[i] = i - 1;
    }
    for (int j = 1; j <= cnt && i * prime[j] <= 5000000; j++) {
      is_prime[i * prime[j]] = 0;
      if (i % prime[j])
        phi[i * prime[j]] = phi[i] * phi[prime[j]];
      else {
        phi[i * prime[j]] = phi[i] * prime[j];
        break;
      }
    }
  }
}

欧拉定理

如果$(a,m)=1$，那么$a^{\phi(m)}\equiv1(mod m)$

即对于$a\in Z_{m}$, a有逆元$\Longleftrightarrow(a,m)=1$

那么$a^{\phi(m)-1}\equiv \frac{1}{a}(mod m)$

费马小定理

设p为质数，且$p \nmid a,那么a^{p-1}\equiv1(mod p)$

逆元

求逆元的两种方法：

• 设m为正整数，$a\in Z_{m}，(a,m)=1$，逆元$\frac{1}{a}=a^{\phi(m)-1}(modm)$

• 设p为质数，$a\in Z_{p},0<a<p,$逆元$\frac{1}{a}=a^{p-2}(modp)$

线性同余方程

求同余方程$ax\equiv c(modb)$的解

方程$ax+by=c$与方程$ax\equiv c(mod b)$是等价的，有整数解的充要条件为$gcd(a,b)|c$。

根据扩展欧几里得求解

最后通解为

$$x=x_{0}+\frac{b}{gcd(a.b)}*t,y=y_{0}-\frac{a}{gcd(a.b)}*t$$

若要求x的最小非负整数解

$x=(x_{0} \% t +t)\% t ,t=\frac{b}{gcd(a,b)}$

// C++ Version
int ex_gcd(int a, int b, int& x, int& y) {
  if (b == 0) {
    x = 1;
    y = 0;
    return a;
  }
  int d = ex_gcd(b, a % b, x, y);
  int temp = x;
  x = y;
  y = temp - a / b * y;
  return d;
}
​
bool liEu(int a, int b, int c, int& x, int& y) {
  int d = ex_gcd(a, b, x, y);
  if (c % d != 0) return 0;
  int k = c / d;
  x *= k;
  y *= k;
  return 1;
}

同余方程组

$$\begin{cases} x&\equiv a_1\pmod {m_1}\\ x&\equiv a_2\pmod {m_2}\\ &\vdots\\ x&\equiv a_k\pmod {m_k}\\ \end{cases}$$

当k=2时，$x=y_1 m_1+a_1=y_2 m_2 +a_2$,即$-y_1 m_1+y_2 m_2=a_1-a_2$，由扩展欧几里得，$-y_1=(y_{0}+k\frac{m_2}{(m_1,m_2)})$,故$x=y_1 m_1+a_1=m_1 y_0+k\frac{m_1 m_2}{(m_1,m_2)}+a_1=x_0+k[m_1,m_2]$

当且仅当$(m_1,m_2)|a_1-a_2$时有解，解的形式为$x\equiv x_0 mod[m_1,m_2]$

当k不等于2时，每次对两个同余方程进行操作，操作k次，可得解的形式为$x=x_0mod[m_1,m_2,…,m_k]$

解一元线性同余方程组

$$\begin{cases} a_1x+b_1&\equiv 0\pmod {m_1}\\ a_2x+b_2&\equiv 0\pmod {m_2}\\ &\vdots\\ a_kx+b_k&\equiv 0\pmod {m_k}\\ \end{cases}$$

可转化为

$$\begin{cases} x&\equiv -a_1^{-1}b_1\pmod {m_1}\\ x&\equiv -a_2^{-1}b_2\pmod {m_2}\\ &\vdots\\ x&\equiv -a_k^{-1}b_k\pmod {m_k}\\ \end{cases}$$

同余方程组的构造解

中国剩余定理

设$m_1,m_2,…,m_k$是两两互质的k个正整数

则方程组$\begin{cases} x\equiv a_1(mod&m_1)\\ x\equiv a_2(mod&m_2) \\ \vdots \\x\equiv a_k(mod&m_k) \end{cases} 的解为x=\sum_{i=1}^k M_i' M_i a_i(mod m)$

其中$M=m_1 m_2 …m_k,M_i=M/m_i,M_i' M\equiv1(mod m_i)$

int exgcd(int a, int b, int& x, int& y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    int d = exgcd(b, a % b, y, x);
    y -= (a / b) * x;
    return d;
}
//注意在实际调用时，*a是模数（相当于同余式中的m），*r是余数（相当于同余式中的a）
ll CRT(ll k, ll* a, ll* r) {
    ll n = 1, ans = 0;
    for (int i = 1; i <= k; i++) n = n * r[i];
    for (int i = 1; i <= k; i++) {
        ll m = n / r[i], b, y;
        exgcd(m, r[i], b, y);  // b * m mod r[i] = 1
        ans = (ans + a[i] * m * b % n) % n;
    }
    return (ans % n + n) % n;
}

扩展中国剩余定理

在中国剩余定理的基础上 $\begin{cases} x\equiv a_1(mod&m_1)\\ x\equiv a_2(mod&m_2) \\ \vdots \\x\equiv a_k(mod&m_k) \end{cases}$

若$m_1 ,m_2,…,m_k$ 不一定两两互质，那么此时可能会存在无解的情况，

//偷绒绒的板子
ll A[N], M[N];
ll exGCD(ll a, ll b, ll &x, ll &y) {
    if (!b) {
        x = 1, y = 0;
        return a;
    }
    ll gcd = exGCD(b, a % b, x, y), tmpx = x;
    x = y;
    y = tmpx - a / b * y;
    return gcd;
}
ll mul(ll a, ll b, ll p) {
    ll ans = 0;
    for (; b; b >>= 1, (a <<= 1) %= p)
        if (b & 1)(ans += a) %= p;
    return ans;
}
ll exCRT(int n) {
    ll a1 = A[1], m1 = M[1];
    for (int i = 2; i <= n; ++i) {
        ll a2 = (A[i] % M[i] + M[i]) % M[i], m2 = M[i], x, y;
        ll gcd = exGCD(m1, m2, x, y);
        ll del = ((a1 - a2) % m2 + m2) % m2;
        if (del % gcd)return -1ll;
        ll k1 = -mul(x, del / gcd, m2 / gcd);
        a1 += m1 * k1;
        m1 = m1 / gcd * m2;
        a1 = (a1 % m1 + m1) % m1;
    }
    return a1;
}

扩展欧拉定理

$a^c\equiv a^{c\%\phi(m)+\phi(m)}mod m,if c\geq \phi(m)$