约数

求约数

试除法

• 从小到大枚举，找到一个数的所有小的约数
• 大的部分通过 n / i 实现
• 时间复杂度$O(\sqrt{n})$

 //vector实现
 
 vector<int> get_divisors(int n)
 {
   	vector<int> res;
   	
   	for(int i = 1; i <= n / i; i ++)
   		if(n % i == 0)
   	  {
   			res.push_back(i);
   			if(i != n / i)  res.push_back(n / i);  // 判断i与 n/i 不同，避免重复
   	  }
 
   	sort(res.begin(), res.end());
   	
   	return res;
 }

约数个数

做一些延申，当 $\beta <=\alpha$， 有 $\beta$ 取值为 $0-\alpha$，则每个$\beta$ 有 $\alpha +1$个数可以选择，都构成 d 为 n 的约数（正因数） 所以正 约数个数为$({\alpha }_1+1)({\alpha }_2+1)({\alpha }_3+1).....({\alpha }_k+1)$个

• int 范围内约数个数最大的是 1500 左右（这个级别）

实现

• 先分解质因数，记录下指数
• 再 指数 + 1 相乘得到结果

  unordered_map primes;
  
  for(int i = 2; i <= x / i; i ++)
  {
	 while(x % i == 0)
	 {
		x /= i;  //这步操作后，当x最后一次被整除，x会等于1，所以最后的特判要大于1
		primes[i] ++;
	 }
  }
		  
  if(x > 1)  primes[x] ++;  //特判大于\sqrt(n)的质数
  
  LL ans = 1;
  for(auto i: primes)  ans *= i.second + 1

约数之和

理论

• 依旧是延申，可以知道每个约数其实就是$p_i^{\alpha }$的不同组合
• 所以可以得到 约数之和 就是 $(p_1^0+p_1^1+\cdot \cdot \cdot \cdot \cdot +p_1^{\alpha })(p_2^0+\cdot \cdot \cdot \cdot \cdot p_2^{\alpha })\cdot \cdot \cdot \cdot \cdot (p_k^0+\cdot \cdot \cdot \cdot p_k^{\alpha })$
• 由乘法分配律展开就能得到约数之和

实现

• 利用分解质因数求p和\alpha
• 再利用 t = t * p + 1 的循环实现$(p_1^0+p_1^1+\cdot \cdot \cdot \cdot \cdot +p_1^{\alpha })$

[[include]] <unordered_map>
int main()
{
   unordered_map<int, int> primes;
   int x;
   cin >> x;
   for(int i = 2; i <= x / i; i ++)
 {
   	while(x % i == 0)
     {
   		x /= i;
   		primes[i] ++;
     }
}
 
   if(x > 1) primes[x] ++;  //别忘了检查
 
   for(auto i: primes)
 {
   	int p = i.first, a = i.second;
   	int t = 1;
   	while(a --)  t = (t * p + 1) % m;  //如果有要求
   ans = ans * t % m;
 }
 
   cout << ans << endl;
}

最大公约数

理论

• 欧几里得算法 ^bd4826 $(a,b)=(b,a(\mathrm{mod}b))$ 即 a与b的最大公约数等于b和a模b的最大公约数
• 证明 $a(\mathrm{mod}b)=a-[a/b]\ast b$ a模b等于$a-[a/b](向下取整)\ast b$
  • 又a与b的最大公约数是 b与 $(a-[a/b]\ast b)$的最大公约数（假如a与b的最大公约数为c，c同时可以整除b，和$(a-[a/b]\ast b)$，因为[a/b]是整数，且$(a-[a/b]\ast b)$比a小，都是c的倍数，则没有比c更大的约数（有的话a和b就有更大的约数了）

实现

int gcd(int a, int b)
{
	return b? gcd(b, a % b) : a;
//实现为递归，当b为0时，a的值是其最大公约数，也是其所有递归过程的最大公约数
}