# 阶乘约数

# 题目

定义阶乘 n! = 1 × 2 × 3 × . . . × n。请问 100! （100 的阶乘）有多少个正约数

# 分析

唯一分解定理，也称为正整数的唯一质因子分解定理或正整数的唯一素因子分解定理，是数论中的一个重要定理。该定理表明每个大于 1 的正整数都可以唯一地表示为一组质数的乘积。

具体表述如下：
对于任意一个大于 1 的正整数 n，存在一组质数 p1, p2, ..., pk，以及对应的正整数幂次 a1, a2, ..., ak，使得 n = p1^a1 * p2^a2 * ... * pk^ak，并且这个表示方法是唯一的，即如果将 n 用其他质数的乘积表示，那么这些质数和对应的幂次必然与上述表示完全相同。

例如，对于正整数 60，它可以表示为 2^2 * 3^1 * 5^1。这就是唯一分解定理的应用，将一个数分解为质数的乘积。

唯一分解定理是数论中的基本定理之一，它对于证明其他数论性质和算法有着重要的作用。

例如，对于正整数 60，它可以表示为 2^2 * 3^1 * 5^1。这就是唯一分解定理的应用，将一个数分解为质数的乘积。

唯一分解定理是数论中的基本定理之一，它对于证明其他数论性质和算法有着重要的作用。

# 代码

	#include<bits/stdc++.h>
	using namespace std;
	const int N = 1e2 + 10;
	int cnt[N]; //cnt [i] 存的是质因子 i 的幂次
	signed main(){
	for(int i = 1 ; i <= 100 ; i ++){
	int x = i;
	// 质因子分解
	for(int j = 2 ; j * j <= x ; j ++){
	if(x % j == 0) while(x % j == 0) x /= j , cnt[j] ++ ; //j 是其中一个质因子
	}
	if(x > 1) cnt[x] ++ ; //x 是其中一个质因子
	}
	long long ans = 1;
	// 约数定理
	for(int i = 1 ; i <= 100 ; i ++) if(cnt[i] != 0) ans *= (cnt[i] + 1);
	cout << ans << '\n';
	return 0;
	}

# 求值

# 题目

学习了约数后，小明对于约数很好奇，他发现，给定一个正整数 t，总是可以找到含有 t 个约数的整数。小明对于含有 t 个约数的最小数非常感兴趣，并把它定义为 St 。例如 S1 = 1, S2 = 2, S3 = 4, S4 = 6, . . . 。现在小明想知道，当 t = 100 时，St 是多少？即 S100 是多少？

# 分析

枚举

# 代码

	#include<bits/stdc++.h>
	using namespace std;
	// 判断 x 的因子个数是否为 100
	bool check(int x){
	int cnt = 0;
	for(int i = 1 ; i * i <= x ; i ++) {
	if(x % i == 0) {
	if(x / i == i) cnt += 1;
	else cnt += 2;
	}
	}

	signed main(){
	for(int i = 1 ; ; i ++) if(check(i)) {
	cout << i << '\n';
	break ;
	}
	return 0;
	}

# 循环小数

# 问题

【问题描述】已知 S 是一个小于 1 的循环小数，请计算与 S 相等的最简真分数是多少。例如 0.3333 . . . 等于 1 /3 ，0.1666 . . . 等于 1 /6 。

【输入格式】输入第一行包含两个整数 p 和 q，表示 S 的循环节是小数点后第 p 位到第 q 位。第二行包含一个 q 位数，代表 S 的小数部分前 q 位。其中，1 ⩽ p ⩽ q ⩽ 10。

【输出格式】输出两个整数，用一个空格分隔，分别表示答案的分子和分母。

【样例输入】 1 6 142857

【样例输出】 1

# 分析

n × 100 = a + n.

x = a, y = 99.

x = b × (10⌊lg(a)⌋+1 − 1) + a, y = (10⌊lg(b)⌋+1) × (10⌊lg(a)⌋+1 − 1).

# 代码

	#include<bits/stdc++.h>
	using namespace std;
	signed main(){
	int p , q;
	string s;
	cin >> p >> q >> s;
	if(p == ) { // 情况：n 为纯循环小数
	long long a = ;
	for(int i = 0 ; i < s.size() ; i ++) a = a * 10 + s[i] - '0';
	long long x = a , y = pow(10 , (int)log10(a) + ) - ;
	cout << x / __gcd(x , y) << " " << y / __gcd(x , y) << '\n'; // 最简形式
	}
	else { // 情况： n 为混循环小数
	long long a = , b = ;
	for(int i = 0 ; i < p - ; i ++) b = b * 10 + s[i] - '0';
	for(int i = p - ; i < q ; i ++) a = a * 10 + s[i] - '0';
	long long x = b * (pow(10 , (int)log10(a) + ) - ) + a , y = pow(10 , (int)log10(b)
	+ ) * (pow(10 , (int)log10(a) + ) - );
	cout << x / __gcd(x , y) << " " << y / __gcd(x , y) << '\n'; // 最简形式
	}
	return 0;
	}

# 等差数列

# 题目

【问题描述】数学老师给小明出了一道等差数列求和的题目。但是粗心的小明忘记了一部分的数列，只记得其中 N 个整数。现在给出这 N 个整数，小明想知道包含这 N 个整数的最短的等差数列有几项。

【输入格式】输入的第一行包含一个整数 N。第二行包含 N 个整数 A1, A2, . . . , AN。(注意 A1 ∼ AN 并不一定是按等差数列中的顺序给出)。其中，2 ⩽ N ⩽ 105 , 0 ⩽ Ai ⩽ 109。

【输出格式】输出一个整数表示答案。

【样例输入】 5 2 6 4 10 20

【样例输出】 10

# 分析

项数 = [(末项 An − 首项 A1)/ 公差 d] +1

# 代码

	#include<bits/stdc++.h>
	using namespace std;
	const int N = 1e5 + ;
	int n , d , a[N];
	signed main(){
	cin >> n;
	for(int i = ; i <= n ; i ++) cin >> a[i];
	sort(a + , a + + n);
	for(int i = ; i <= n ; i ++) d = __gcd(d , a[i] - a[]); // 求差值的最大公约数
	if(!d) cout << n << '\n'; // 如果 d = ，说明 a [1] = a [2] = a [3] = ... = a [n]
	else cout << (a[n] - a[]) / d + << '\n';
	return ;
	}

# 最大比例

# 题目

【问题描述】 X 星球的某个大奖赛设了 M 级奖励。每个级别的奖金是一个正整数。并且，相邻的两个级别间的比例是个固定值。也就是说，所有级别的奖金数构成了一个等比数列，比如：16,24,36,54，其等比值为 3/ 2 。现在，我们随机调查了一些获奖者的奖金数。请你据此推算可能的最大的公比值。

【输入格式】第一行为数字 N (0 < N < 100)，表示接下的一行包含 N 个正整数。第二行 N 个正整数 Xi (Xi < 1012)，用空格分开。每个整数表示调查到的某人的奖金数额。

【输出格式】一个形如 A/B 的分数，要求 A, B 互质。表示可能的最大比例系数测试数据保证了输入格式正确，并且最大比例是存在的。

【样例输入 1】 3 1250 200 32

【样例输出 1】 25/4

【样例输入 2】 4 3125 32 32 200

【样例输出 2】 5/2

# 分析

Q = gcd (q1, q2, . . . , qn−1)。最大公约数也可能是分数

# 代码

	#include<bits/stdc++.h>
	using namespace std;
	const int N = 1e2 + 10;
	int n , cnt;
	long long a[N] , u[N] , d[N];

	long long gcd_sub(long long a , long long b){
	if(a < b) swap(a , b);
	if(b == 1) return a;
	return gcd_sub(b , a / b);
	}

	signed main(){
	cin >> n;
	for(int i = 1 ; i <= n ; i ++) cin >> a[i];
	sort(a + 1 , a + 1 + n);
	for(int i = 2 ; i <= n ; i ++){
	if(a[i] == a[i - 1]) continue ;
	long long g = __gcd(a[i] , a[i - 1]);
	u[++ cnt] = a[i] / g;
	d[cnt] = a[i - 1] / g;
	}
	long long x = u[1] , y = d[1];
	for(int i = 2 ; i <= cnt ; i ++){
	x = gcd_sub(x , u[i]);
	y = gcd_sub(y , d[i]);
	}
	cout << x << "/" << y << '\n';
	return 0;
	}

数论

# 阶乘约数

# 题目

# 分析

# 代码

# 求值

# 题目

# 分析

# 代码

# 循环小数

# 问题

# 分析

# 代码

# 等差数列

# 题目

# 分析

# 代码

# 最大比例

# 题目

# 分析

# 代码

思维与贪心

字符串算法