零、写在前面

  这是《算法零基础100讲》 专栏打卡学习的第十一讲了，经过一定的磨合，相信大家都已经养成了习惯，那么，激励的话我就不说了，直接来看今天的内容吧。

一、概念定义

  如何求一个数 $n$ 的因子个数呢？
  朴素的求因子个数的方法为枚举 $[1, n]$ 的数进行余数为 0 判定，复杂度为 $O(n)$，这里加入一个小优化，如果 $m$ 为 $n$ 的因子，那么必然 $\frac nm$ 也为 $n$ 的因子，不妨设 $m \le \frac nm$，则有 $m \le \sqrt n$，所以只要枚举从 $[1, \sqrt n]$ 的因子然后计数即可，复杂度变为 $O(\sqrt n)$。
  根据 算术基本定理，容易发现， $n$ 的因子一定是 $p_1、p_2、...、p_k$ 的组合，并且 $p_1$ 可以取的个数为 $[0, e_1]$， $p_2$ 可以取的个数为 $[0, e_2]$， $p_k$ 可以取的个数为 $[0, e_k]$，所以根据乘法原理，总的因子个数记为 $g(n)$，等于 $e_i+1$ 的连乘，即：

$$g(n) = \prod_{i=1}^{k} (e_i + 1)$$

  算法时间复杂度即求素因子分解的时间复杂度，为 $O(s)$。

二、题目描述

  给定 $x,y(x, y \lt 2^{31})$，求 $x^y$ 的因子数 $\mod p$。

三、算法详解

  由于这里的 $x^y$ 已经是天文数字，利用上述的枚举法已经无法满足要求，所以我们需要换个思路。考虑到任何整数都能表示成素数的乘积，那么 $x^y$ 也不例外，我们首先将 $x$ 进行因数分解，那么 $x^y$ 可以表示成如下形式：

$$\begin{aligned} x^y &= (p_1^{e_1}p_2^{e_2}p_3^{e_3}...p_k^{e_k}) ^ y \\ &= p_1^{ye_1}p_2^{ye_2}p_3^{ye_3}...p_k^{ye_k} \end{aligned}$$

  直接套用因子数公式，得到：

$$g(x^y) \ mod \ p = \prod_{i=1}^{k} (ye_i + 1) \ mod \ p$$

四、源码剖析

  首先准备一个结构体factor，用来表示它的素因子是什么，以及该素因子的个数。

struct factor {
	int prime, count;
	factor() :prime(0), count(0) {}
	factor(int p, int c) : prime(p), count(c) {}
	void print() {
		printf("(%d, %d)\n", prime, count);
	}
};

  然后，利用一个素因子分解的接口Factorization(int n, vector <factor>& ans)来实现枚举素因子的分解。即对于 $n=252$ 的情况，函数计算完毕后，ans中存的结果是：[ (2,2), (3,2), (7,1) ]

void Factorization(int n, vector <factor>& ans) {
	ans.clear();
	if(n == 1) {
		return ;                           // (1)
	}
	// 素数试除 
	for(int i = 1; i <= primes[0]; i++) {  // (2)
		if(n % primes[i] == 0) {           // (3)
			factor f(primes[i], 0);        // (4)
			while( !(n % primes[i]) ) {    // (5)
				n /= primes[i];
				f.count ++;            
			}
			ans.push_back(f);              // (6)
		}
		if(n == 1) {
			return ;
		}
	}
	ans.push_back( factor(n, 1) );        // (7)
}

• $(1)$ 1 不需要素因子分解。
• $(2)$ primes[0]代表在进行素数筛选时，素数的个数，素数筛选的内容，参考：《算法零基础100讲》(第8讲) 素数筛选。
• $(3)$ 对每一个素数进行试除；
• $(4)$ 调用构造函数；
• $(5)$ 如果存在prime[i]这个素因子，则将它除掉，并且个数计数自增；
• $(6)$ 记录一个素因子信息；
• $(7)$ 所有素数都除不尽，说明它本身是一个素数；

五、推荐专栏

六、习题练习

《算法零基础100讲》(第11讲) 因子数