约数

约数个数定理

$n = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k}$

$n$ 的约数个数 $(a_1+1)(a_2+1)\cdots (a_k+1)$

$24 = 2^3 \times 3^1$

24的约数个数是 $(3 + 1)(1 + 1) = 8$

约数和定理

$n = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k}$

$n$ 的约数和 $(p_1^0 + p_1^1+ \cdots +p_1^{a_1})(p_2^0 + p_2^1+ \cdots +p_2^{a_2})\cdots (p_k^0 + p_k^1+ \cdots +p_k^{a_k})$

等比数列求和？
可以用数学课上学的公式
$r^0 + r^1 + \cdots r^{n-1} = \frac{r^n - 1}{r - 1}$
数学课上会强调，公比不能为1
计算机中不用这个公式，因为会涉及到除法

约数的k次方和

完全数

高合成数

在int范围内比较大的高合成数（任何比它小的自然数的约数个数均比这个数的约数个数少）
735134400 = 2^6 * 3^3 * 5^2 * 7 * 11 * 13 * 17，1344个约数
1102701600 = 2^5 * 3^4 * 5^2 * 7 * 11 * 13 * 17，1440个约数
1396755360 = 2^5 * 3^3 * 5 * 7 * 11 * 13 * 17 * 19，1536个约数
2095133040 = 2^4 * 3^4 * 5 * 7 * 11 * 13 * 17 * 19，1600个约数

参考题目

P5834 [USACO19DEC]MooBuzz S

https://www.luogu.com.cn/problem/P5834

题目描述

Farmer John 的奶牛们最近成为了一个简单的数字游戏“FizzBuzz”的狂热玩家。这个游戏的规则很简单：奶牛们站成一圈，依次从一开始报数，每头奶牛在轮到她的时候报一个数。如果一头奶牛将要报的数字是 $3$ 的倍数，她应当报 Fizz 来代替这个数。如果一头奶牛将要报的数字是 $5$ 的倍数，她应当报 Buzz 来代替这个数。如果一头奶牛将要报的数字是 $15$ 的倍数，她应当报 FizzBuzz 来代替这个数。于是这个游戏的开始部分的记录为：

1, 2, Fizz, 4, Buzz, Fizz, 7, 8, Fizz, Buzz, 11, Fizz, 13, 14, FizzBuzz, 16

由于词汇的匮乏，奶牛们玩的 FizzBuzz 中用Moo 代替了 Fizz、Buzz、FizzBuzz。于是奶牛版的游戏的开始部分的记录为：

1, 2, Moo, 4, Moo, Moo, 7, 8, Moo, Moo, 11, Moo, 13, 14, Moo, 16

给定 $N$ ，请求出这个游戏中第 $N$ 个被报的数。

输入格式

输入包含一个整数 $N$ 。

输出格式

输出游戏中被报出的第 $N$ 个数。

样例 #1

样例输入 #1

样例输出 #1

提示

关于部分分：

测试点 $1$ 为样例。

测试点 $2\sim 5$ 满足 $N\le 10^6$ 。

对于 $100\%$ 的数据， $1 \leq N \leq 10^9$

供题：Brian Dean

参考代码

#include <bits/stdc++.h>
using namespace std;
long long calc(long long n)
{
	return n - n / 3 - n / 5 + n / 15;
}
int main()
{
	long long n;
	cin >> n;
	long long L = 0;
	long long R = 2 * n;
	while (L < R - 1)
	{
		int M = (L + R) / 2;
		if (calc(M) < n)
		{
			L = M;
		}
		else
		{
			R = M;
		}
	}
	cout << R << endl;
	return 0;
}

约数