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

欧拉函数

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

ϕ(n)=(p1−1)p1α1−1∗(p2−1)p2α2−1∗…∗(pk−1)pkαk−1=n∗Πi=1spi−1pi\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为奇数，ϕ(n)=ϕ(2n)\phi(n)=\phi(2n)

  • n=∑d∣nϕ(d)n=\sum_{d|n}\phi(d)

  • if n=pkn=p^{k},then ϕ(n)=pk−pk−1\phi(n)=p^k-p^{k-1}

  • 当n>2时，n是偶数

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

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

筛法求欧拉函数

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

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

如果n′modp1=0n'modp_{1}=0,ϕ(n)\phi(n)=p1p_{1}*ϕ(n′)\phi(n')

如果n′modp1≠0n'modp_{1}\neq0,ϕ(n)\phi(n)=(p1−1)(p_{1}-1)*ϕ(n′)\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,m)=1，那么aϕ(m)≡1(modm)a^{\phi(m)}\equiv1(mod m)

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

那么aϕ(m)−1≡1a(modm)a^{\phi(m)-1}\equiv \frac{1}{a}(mod m)

费马小定理

设p为质数，且p∤a,那么ap−1≡1(modp)p \nmid a,那么a^{p-1}\equiv1(mod p)

逆元

求逆元的两种方法：

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

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

线性同余方程

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

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

根据扩展欧几里得求解

最后通解为

x=x0+bgcd(a.b)∗t,y=y0−agcd(a.b)∗tx=x_{0}+\frac{b}{gcd(a.b)}*t,y=y_{0}-\frac{a}{gcd(a.b)}*t

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

x=(x0%t+t)%t,t=bgcd(a,b)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;
}

同余方程组

{x≡a1(modm1)x≡a2(modm2)⋮x≡ak(modmk)\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=y1m1+a1=y2m2+a2x=y_1 m_1+a_1=y_2 m_2 +a_2,即−y1m1+y2m2=a1−a2-y_1 m_1+y_2 m_2=a_1-a_2，由扩展欧几里得，−y1=(y0+km2(m1,m2))-y_1=(y_{0}+k\frac{m_2}{(m_1,m_2)}),故x=y1m1+a1=m1y0+km1m2(m1,m2)+a1=x0+k[m1,m2]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]

当且仅当(m1,m2)∣a1−a2(m_1,m_2)|a_1-a_2时有解，解的形式为x≡x0mod[m1,m2]x\equiv x_0 mod[m_1,m_2]

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

解一元线性同余方程组

{a1x+b1≡0(modm1)a2x+b2≡0(modm2)⋮akx+bk≡0(modmk)\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}

可转化为

{x≡−a1−1b1(modm1)x≡−a2−1b2(modm2)⋮x≡−ak−1bk(modmk)\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}

同余方程组的构造解

中国剩余定理

设m1,m2,…,mkm_1,m_2,…,m_k是两两互质的k个正整数

则方程组{x≡a1(modm1)x≡a2(modm2)⋮x≡ak(modmk)的解为x=∑i=1kMi′Miai(modm)\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=m1m2…mk,Mi=M/mi,Mi′M≡1(modmi)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;
}

扩展中国剩余定理

在中国剩余定理的基础上 {x≡a1(modm1)x≡a2(modm2)⋮x≡ak(modmk)\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}

若m1,m2,…,mkm_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;
}

扩展欧拉定理

ac≡ac%ϕ(m)+ϕ(m)modm,ifc≥ϕ(m)a^c\equiv a^{c\%\phi(m)+\phi(m)}mod m,if c\geq \phi(m)

Last updated