[数论第二节]欧拉函数/快速幂/扩展欧几里得算法

证明：

• 互质：两数的公共因子只有1
• 去掉所有与N有(大于1的)公共因子的数，剩下的数就是与N互质的数
• 对N的所有质因子(p_k)，去掉所有(underline{质数p_k的倍数})(与N有公共因子的数)，(underline{每个质数的倍数})个数为 (frac{N}{p_k})，即$$N - frac{N}{p_1} - frac{N}{p_2} - ··· -frac{N}{p_n}$$
• 对于数 (p_i·p_j)，在去掉 (p_i) 的倍数和去掉 (p_j) 的倍数的过程中去除了两次，所以要加上一次，即$$N - (frac{N}{p_1} + frac{N}{p_2} + ··· +frac{N}{p_n}) + (frac{N}{p_1p_2} + frac{N}{p_1p_3} + ··· +frac{N}{p_{n-1}p_n})$$
• 对于数 (p_i·p_j·p_k)，在去掉(p_k)的倍数的过程中被去掉了三次，在加上合数 (p_i·p_j) 的过程中被加上了三次，所以合数 (p_i·p_j·p_k) 没有被去掉，因此要去掉它，即$$N - (frac{N}{p_1} - frac{N}{p_2} - ··· -frac{N}{p_n}) + (frac{N}{p_1p_2} + frac{N}{p_1p_3} + ··· +frac{N}{p_{n-1}p_n}) - (frac{N}{p_1p_2p_3} + frac{N}{p_1p_2p_4} + ··· +frac{N}{p_{n-2}p_{n-1}p_n})$$
• 对于合数 (p_i·p_j·p_k·p_m) 同理，归纳递推可知，所有质数个数为：$$N - displaystylesum^n_{i=1}{frac{N}{p_i}}+displaystyle sum_{1<=i<j<=n}{frac{N}{p_ip_j}}-displaystyle sum_{1<=i<j<k<=n}{frac{N}{p_ip_jp_k}}+···+(-1)^{2n-1}displaystyle sum_{1<=i<j<k<···<=n}{frac{N}{p_ip_jp_k···p}}$$
• 同样基于容斥原理：

  • [|Acup Bcup C|=|A|+|B|+|C|-|Acap B|-|Acap C|-|Bcap C|+|Acap Bcap C| ]

  • [|displaystyle cup_{i=1}^n A_i |=sum_{i}|A_i|-sum_{i,j} |A_i cap A_j|+ldots +(-1)^{n+1}|cap_{i=1}^n A_i | ]

  • 与N有(大于1的)公共因子的个数 =| (p_i) 的倍数的个数| - |(p_ip_j) 的倍数的个数| + |(p_ip_jp_k) 的倍数的个数 ··· ((-1)^{n+1}) |(p_ip_j···p_n) 的倍数的个数|
• 将上式因式分解后：$$N(1-frac{1}{p_1})(1-frac{1}{p_2})···(1-frac{1}{p_n})$$

容斥原理：

int res = a;
for(int i = 2; i <= a / i; ++ i){
    if(a % i == 0){//i为质因子
        res = res / i * (i - 1);//套公式
        while(a % i == 0) a /= i;//把因子除干净
    }
}
if(a > 1) res = res / a * (a - 1);//最后一个因子可能大于sqrt(a)

筛选法：

• 利用线性筛选质数的过程求出每个数的欧拉函数
• 欧拉函数为积性函数，当a与b互质时有$$varphi(a·b)=varphi(a)·varphi(b)$$
• 当i为质数时，$$varphi(i)=i-1$$
• 当(frac{i}{p_j} = 0)时，(p_j)为i的质因子，此时(p_j·i)的质因子与i的质因子完全相同，所以 $$varphi(pj·i)=pj·i·(1-frac{1}{p_1})(1-frac{1}{p_2})···(1-frac{1}{p_n})=p_j·varphi(i)$$
• 当(frac{i}{p_j} neq 0)时，(p_j)不为i的质因子，此时(p_j·i)的质因子比i的质因子多一个(p_j)，所以 $$varphi(pj·i)=pj·i·(1-frac{1}{p_1})(1-frac{1}{p_2})···(1-frac{1}{p_n})(1-frac{1}{p_j})=p_j·varphi(i)·(1-frac{1}{p_j})=(p_j - 1)·varphi(i)$$
• 代码：

  const int N = 1e6 + 10;
  typedef long long LL;
  int primes[N], cnt;//质数数组，下标
  int st[N];//标记为合数
  int phi[N];//欧拉函数
  int n;
  
  LL get_eulers(int n){
      phi[1] = 1;
      for(int i = 2; i <= n; ++ i){
          if(!st[i]){
              primes[ ++ cnt] = i;
              phi[i] = i - 1;//质数i的欧拉函数为i - 1
          }
          for(int j = 1; primes[j] <= n / i; ++ j){
              int pj = primes[j];
              st[pj * i] = 1;
              if(i % pj == 0){//i是合数
                  phi[pj * i] = pj * phi[i];//pj为i的质因子
                  break;
              }
              else phi[pj * i] = (pj - 1) * phi[i];//pj不是i的因子
          }
      }
      
      LL ans = 0;
      for(int i = 1; i <= n; ++ i) ans += phi[i];
      return ans;
  }
  

欧拉函数的应用

• 欧拉定理

  • 若a与n互质，则$$a^{varphi(n)}pmod nequiv1$$
  • 证明：
    • 若a与b互质，且(apmod bneq 0)则(apmod b) 也与b互质
    • 设(a_1,a_2,a_3···a_{varphi(n)}) 为1~n中的所有与n互质的数
    • 每个数同时乘上a得(a·a_1,a·a_2,a·a_3···a·a_{varphi(n)}) 由于a也与n互质，所以乘a后所得的数也全部与n互质
    • 将每个数mod n，取模后的每个数都在1~n范围内，并且仍然都与n互质，显然取模后的这几个数就是原来的几个数，只不过数的顺序可能发生了变化
    • 将所有数相乘，则有$$a·a_1·a·a_2·a·a_3···a·a_{varphi(n)} pmod n=a_1·a_2·a_3···a_{varphi(n)}$$
    • 所以有：$$a^{varphi(n)}·(a_1a_2a_3···a_{varphi(n)})pmod n equiv (a_1·a_2·a_3···a_{varphi(n)})$$即$$a^{varphi(n)}pmod nequiv1$$
    • 特别地，当n为质数时，(a^{n-1}pmod nequiv1) 为费马定理

typedef long long LL;
//求a^k mod b
int qmi(int a, int k, int b){
	int res = 1;
	while(k){
		if(k & 1) res = (LL)res * a % b;//k的当前位非0，则将a累乘到答案
		k >>= 1;//k右移一位
		a = (LL)a * a % b;//a的幂倍增
	}
	return res;
}

快速幂求逆元

• 若b与p互质，且 (b|a)，(frac a b=a·x pmod p) ，则x为b的逆元
• 两边乘b有$$a=a·b·x pmod p$$
• 所以有$$b·x=1 pmod p$$
• 若p是质数，有费马定理$$b^{p-1} = 1 pmod p$$则$$x=b^{p-2}$$
• 若p不是质数，有欧拉定理$$b^{varphi(p)}=1 pmod p$$则$$x=b^{varphi(p)- 1}$$
• 代码：

  int qmi(int a, int b, int p){
  	略...
  }
  if(b与q互质){ //互质是有解的前提
  	if(p为质数) cout << qmi(b, p - 2, p);
  	else cout << qmi(b, phi[p] - 1, p);
  }else 无解
  

裴蜀定理：对于任意正整数a,b, 都一定存在整数x,y, 使得(ax+by=gcd(a,b)), 并且 (gcd(a,b)) 一定是a与b能构造出来的最小公约数

扩展欧几里得算法就是求这样的x，y

用于求解方程 (ax+by=gcd(a,b)) 的解

当 (b=0) 时 (ax+by=a) 故而 (x=1,y=0)

当 (b neq 0) 时,因为

而

故而 $$x=y_1,quad y=x_1-lfloor a/b rfloor ·y_1$$

代码：

int exgcd(int a, int b, int &x, int &y){
    if(!b){ //b = 0时，ax + by = gcd(a, 0) = a,所以x = 1, y = 0;
        x = 1, y = 0;
        return a;
    }else {
        int d = exgcd(b, a % b, x, y);//交换a与b，x与y
        int t = x;
        x = y;//x1 = y2
        y = t - a / b * y;//y1 = x2 - a / b * y2
        return d;
    }
}

//简化版
void exgcd(int a, int b, int &x, int &y){
    if(!b){
        x = 1, y = 0;
        return a;
    }else{
	    int d = exgcd(b, a % b, y, x);
	    y -= a / b * x;
	    return d;
    }    
}

扩展欧几里得求解线性同余方程

• 线性同余方程：$$ax equiv b pmod m$$ 其中a，x，b，m均为整数，x为未知数，方程等价于 (ax=km+b)，也等价于 $$ax+mk=b$$其中x,k均为未知数
• 方程形如：$$ax+by=c$$ 的直线方程，解(x,y)为直线上散列的点
• 求出a，b的最大公约数(d = gcd(a,b))，方程化为 $$d(x frac a d+yfrac b d)=c$$易知其中 (x frac a d+yfrac b d) 为整数，所以要求 (d|c)，故 $$c=k·d=k·gcd(a,b)$$
• 所以线性同余方程(ax equiv b pmod m)有解的充要条件为b为(gcd(a,m))的倍数
• 当 (b neq k'·gcd(a,m)) 时((k') 为整数)，方程无解
• 当 (b = k'·gcd(a,m)) 时，先用扩展欧几里得求出方程 (ax+mk=gcd(a,m)) 的特解((x,k))，可知 (ax+mk=b) 方程的解为 (frac {b}{gcd(a,m)}·(x,k)) ，所以原式的解为 (frac {b}{gcd(a,m)}·x)
• 代码：

  const int N = 1e5 + 10;
  typedef long long LL;
  int n; 
  int a, b, m;
  int x, y;
  //扩展欧几里得算法
  int exgcd(int a, int b , int &x, int &y){
      if(!b){
          x = 1, y = 0;
          return a;
      }else{
          int t = exgcd(b, a % b, y, x);
          y -= a / b * x;
          return t;
      }
  }
  
  int main(){
      cin >> n;
      while(n -- ){
          cin >> a >> b >> m;
          int t = exgcd(a, m, x, y);
          //b是gcd(a,m)的倍数才有解
          if(b % t != 0) cout << "impossible" << endl;
          else cout << (LL)x * (b / t) % m << endl;//特解乘上倍数
      }
      return 0;
  }