蓝桥杯c++算法学习【4】之简单数论（阶乘约数、求值、循环小数、等差数列、最大比例：：：非常典型的必刷例题！！！）

 

别忘了请点个赞+收藏+关注支持一下博主喵！！！!

关注博主，更多蓝桥杯nice题目静待更新:)

简单数论

一、阶乘约数

【问题描述】

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

【答案提交】

        这是一道结果填空题，你只需要算出结果后提交即可。本题的结果作为一个整数，在 提交答案时只填写这个整数，填写多余的内容将无法得分。

运用到的两个数学定理

1. 唯一分解定理（Fundamental Theorem of Arithmetic）

唯一分解定理，也称为算术基本定理，指出每一个大于1的正整数都可以唯一地表示为若干个质数的乘积，不考虑因子的顺序。具体来说：

对于任意正整数 nn，存在唯一的质数集合 p1,p2,…,pkp1​,p2​,…,pk​ 和对应的正整数指数 e1,e2,…,eke1​,e2​,…,ek​，使得：

n=p1e1×p2e2×⋯×pkekn=p1e1​​×p2e2​​×⋯×pkek​​

其中 p1,p2,…,pkp1​,p2​,…,pk​ 是互不相同的质数，e1,e2,…,eke1​,e2​,…,ek​ 是正整数。

例如，考虑数字 60： 60=22×31×5160=22×31×51

2. 约数定理（Divisor Function）

约数定理 是基于唯一分解定理的一个推论，它提供了计算一个数的所有正约数个数的方法。具体来说：

如果一个正整数 nn 的质因数分解为： n=p1e1×p2e2×⋯×pkekn=p1e1​​×p2e2​​×⋯×pkek​​

那么 nn 的所有正约数的个数 d(n)d(n) 可以通过以下公式计算： d(n)=(e1+1)×(e2+1)×⋯×(ek+1)d(n)=(e1​+1)×(e2​+1)×⋯×(ek​+1)

3. 解释

1. 质因数分解：

   • 将 nn 分解为若干个质数的乘积，每个质数的指数表示该质数在分解中的次数。

2. 约数个数公式：

   • 每个质数 pipi​ 的指数 eiei​ 可以取 0 到 eiei​ 之间的任意值，共有 ei+1ei​+1 种选择。
   • 因此，所有质数的选择组合起来，总共有 (e1+1)×(e2+1)×⋯×(ek+1)(e1​+1)×(e2​+1)×⋯×(ek​+1) 种不同的组合方式，这就是 nn 的所有正约数的个数。

4. 示例

考虑数字 60： 60=22×31×5160=22×31×51

根据约数定理： d(60)=(2+1)×(1+1)×(1+1)=3×2×2=12d(60)=(2+1)×(1+1)×(1+1)=3×2×2=12

验证： 60 的所有正约数为：1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60，共 12 个。

5. 总结

• 唯一分解定理：每个正整数可以唯一地表示为若干个质数的乘积。
• 约数定理：基于唯一分解定理，提供了一个计算一个数的所有正约数个数的方法。

本题解析：

这题我们将用到唯一分解定理和约数定理

        题目要我们求的是100!的约数个数。约数即因子，如果按照最简单的方法来做题，我们会习惯性地先计算出100! 的值（设该值为n），再枚举1∼√n中的所有数以找出并统计n 的因子及因子个数，具体代码见参考代码如下。

#include <iostream>
#include <cmath>int main() {long long n = 1, ans = 0; // n 用来表示 100! 的值，ans 用来统计因子个数// 计算 100!for (int i = 1; i <= 100; i++) {n *= i;}// 遍历从 1 到 √n 的所有数for (long long i = 1; i <= sqrt(n); i++) {if (n % i == 0) { // 如果 n 能整除 i// i 和 n / i 都是 n 的因子if (n / i != i) {ans += 2; // 如果 i 和 n / i 是两个不同的因子，则答案的个数 + 2} else {ans += 1; // 如果 i 和 n / i 相同，则答案的个数 + 1}}}std::cout << "100! 的因子个数为: " << ans << std::endl;return 0;
}

        这个方法虽然很简单，但阶乘却是“残酷”的，因为仅仅是20!的值就已经超过1018，而 100! 更是个 “天文数字”。即使我们能求出 100! 的值，也不可能在有限的时间内枚举出100! 的所有因子。所以，我们需要转变思路。

        上述方法的本质是求出所有因子，以此来统计因子的个数。但我们真的需要求出所有的 因子吗?

        不需要。正如上文所说，100!是个“天文数字”，其因子个数可能也十分庞大。在不确定 其因子个数的情况下，想求出其所有的因子显然是不合理的。因此，可以使用唯一分解定理 和约数定理来解决。

        根据唯一分解定理可得，对于一个大于1的整数n，n可以分解质因数：  ，其中pi 表示n的第i个质因子，ai 表示pi 的幂次，表示连乘符号。

        根据约数定理可得，n的正约数的个数为。所 i=1 以我们只要求得100! 的每个质因子对应的幂次即可求出答案。但怎么求100! 的每个质因子 呢? 我们以5!为例简单演示一遍。

         对于5!，其值为1×2×3×4×5=120，其质因子有2,3,5，对应的幂次分别为3,1,1，即 120 =  ×  × 。如果我们对 2,3,4,5 分别做质因数分解，则 2 = ，3 = ，4 = ，5 = 。 不难发现，120 的每个质因子的幂次会等于 2,3,4,5 对应质因子的幂次之和。同理，100! = 1 ×2×3×...×100，所以它的每个质因子的幂次就会等于 2,3,...,100 对应质因子的幂次之 和。因此我们只要对1∼100的每个数做质因子分解，统计每个质因子的幂次，再对应相加 就可得出100! 的每个质因子的幂次。

        求出了每个质因子的幂次后，用约数定理即可求出答案。

        需要注意的是，本题答案很大，需要开 long long 来存储答案。 

参考代码如下 【时间复杂度为 O(100×√100)】

#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]++;}}}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;
}

        最终答案为39001250856960000。 

二、求值

【问题描述】

        学习了约数后，小明对于约数很好奇，他发现，给定一个正整数t，总是可以找到含有 t 个约数的整数。小明对于含有t个约数的最小数非常感兴趣，并把它定义为St。

        例如 S1 = 1, S2 = 2, S3 = 4, S4 = 6,...。

        现在小明想知道，当t=100时，St是多少?即S100是多少?

【答案提交】

        这是一道结果填空题，你只需要算出结果后提交即可。本题的结果作为一个整数，在 提交答案时只填写这个整数，填写多余的内容将无法得分。

解析：

        为了追求简单，我们可以先尝试用枚举法来搜寻答案。方法为从小到大枚举整数，枚举 的同时判断当前枚举到的数是否能作为答案。

         怎么判断一个数是否能作为答案呢?同样为了追求简单，我们可以求出该数的所有因子 以统计因子的个数，再判断因子数是否为100即可。

        判断的结果有两种：能和不能。

        由于我们是从小到大枚举的，所以如果判断的结果为能，那么判断的数就一定会是最小 的、满足条件的答案（结束枚举）；如果判断的结果为不能，就继续枚举，如下图所示。

        显然，这种简单的方法是一定能找到正确答案的，但问题在于该方法找到答案所需要花 费的时间是不确定的，可能需要1年，也可能连1秒都不要。对此，我们可以粗略分析一下。

        假设本题的正确答案为n，那么枚举和判断的总的时间复杂度就为O(n√n)。 

        • 根据唯一分解定理可得，对于一个大于 1 的整数 n，n 可以分解质因数： ，其中pi 表示n的第i个质因子，ai 表示pi 的幂次，表示连乘符号。

        • 根据约数定理可得：n的约数个数为。

        有了这两个定理后，我们就可以任取一个数来确定n的上限。假设我们取的数为x，它 的值为××，由约数定理可得x的约数个数为(4+1)×(4+1)×(3+1)=100。

         因为n的定义是约数个数为100的最小整数，即n⩽x→n⩽××→n⩽162000， 所以O(n√n) 的复杂度可以在很短的时间内得出答案。

        因此，该做法可行，对应参考代码如下所示。   

#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;}}return cnt == 100;
}signed main() {for (int i = 1; ; i++) {if (check(i)) {cout << i << '\n';break;}}return 0;
}

        最终答案为45360。 

拓展提高：：：：

        如果题目要我们求的不是S100，而是S1000（保证所求的值小于等于1018），那怎么办呢? 还能用枚举法一一搜寻答案吗?

        答案是不可以。我们可以求出1∼内每个数的因子个数，会发现其中因子数最多的 也只有240个，远远不及1000个。因此，不难想象S1000的答案是很大很大的，以枚举法的效率在有限的时间内是肯定搜寻不出答案的，如下图所示。

        既然枚举法搜寻不出答案，那要如何搜寻答案呢?

        有一个暴力搜索的办法：通过DFS搜索质因子及质因子的幂次来搜寻答案。

        以求S1000为例，为了方便起见，我们设S1000=n，即设n是约数个数为1000的最小整数。

        那么，根据唯一分解定理，n = 。。根据约数定理，n 的约数个数为 (a1+1) (a2 +1)...(ak +1)。

        为了减少答案的搜寻范围，我们先对答案的性质进行分析。 

        由于n的定义是约数个数为1000的最小整数，所以为了保证n的值最小，须满足a1⩾ a2 ⩾ ... ⩾ ak。      

        什么意思?

        我们来试想一下，如果数值小的质因子的幂次小于数值大的质因子的幂次，那么，只要 我们将两个质因子的幂次交换，n的值就会变小，而约数个数不会改变。

举例说明

        因此可得，数值越小的质因子对应的幂次一定越大，即a1⩾a2⩾...⩾ak。

        另外根据答案的值小于1018，我们还可以再获得以下两条信息。

        （1）n 的质因子个数最多为15。

        （2）n 的质因子的最高幂次为61。

        为什么呢? 我们可以采用反证法来证明。

         • 对于第1条信息，如果n的质因子个数大于15，则必然有

                n ⩾ 16 个最小的质因子相乘

    

        不符合题意，所以n的质因子个数最多为15。 

• 对于第2条信息，如果n的质因子的幂次大于61，则必然有

        不符合题意，所以n的质因子的最高幂次为61。

完成了以上分析后，我们就可以更好地锁定搜索范围，以确定答案。

（1）约数个数为1000 的最小整数。

（2）大小不超过。

（3）质因子个数不超过15。

（4）质因子的幂次不超过61。

（5）数值越小的质因子对应的幂次越大。 

#include <bits/stdc++.h>
using namespace std;int prime[] = {-1, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47}; // prime[0]用于占位，prime[1] ~ prime[15]分别表示第1~15个质数
long long ans = 1e18; // ans表示答案void dfs(int pos, long long val, int num, int up) { // pos表示枚举到的质因子，val表示我们搜寻的数，num表示搜寻的数的质因子个数，up表示质因子的幂次上限if (num > 1000) return; // 约数的个数不超过1000，故当 num > 1000 时结束搜索if (pos > 15) return; // 质因子的个数不超过15，故当 pos > 15 时结束搜索if (num == 1000 && val < ans) { ans = val; return; } // 取约数个数为1000的最小正数for (int i = 1; i <= up; i++) {if (val * prime[pos] > ans) break; // 剪枝val *= prime[pos];// 由于质因子越大幂次越小，所以下一个质因子的幂次不能大于i（当前质因子的幂次）dfs(pos + 1, val, num * (i + 1), i);}
}signed main() {dfs(1, 1, 1, 61);cout << ans << '\n';return 0;
}

        此外我们也可以使用动态规划解决，即定义dp[i][j]，其含义为由前i个质数作为因子组 成约数个数为j的最小整数。

        根据约数定理，我们可轻松推出dp的状态转移方程。 

pirme[i]表示第i个质数，i⩽15，prime[i]k⩽1018。 、       

        答案为dp[15][1000]。 

参考代码如下【时间复杂度为O(15×1000×log1018)】

#include <bits/stdc++.h>
using namespace std;int prime[] = {-1, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47}; // prime[0]用于占位，prime[1]~prime[15]分别表示第1~15个质数
long long dp[16][1001], INF = 1e18;signed main() {memset(dp, 0x3f, sizeof(dp)); // 初始化为无穷大dp[0][1] = 1;for (int i = 1; i <= 15; i++) {for (int j = 1; j <= 1000; j++) {long long p = 1;for (int k = 0; k <= 61; k++) { // 幂次的范围为0~61// 约数个数不能大于1000，即 j * (k + 1) <= 1000// INF = 10^18，答案的值不超过10^18，即 prime[i] * p <= INFif (j * (k + 1) > 1000 || INF / prime[i] < p) break;if (k > 0) p *= prime[i]; // 第 k 轮循环时，p = prime[i]^kif (dp[i][j * (k + 1)] / p >= dp[i - 1][j]) dp[i][j * (k + 1)] = p * dp[i - 1][j];}}}cout << dp[15][1000] << '\n';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。

【输出格式】

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

【样例输入】

        

【样例输出】

        17

解析：

        在开始做题之前，我们先来看看循环小数的定义：一个数的小数部分从某一位起，有一 个或多个数字依次重复出现（循环节）的无限小数叫循环小数。循环小数又分以下两种。

        • 纯循环小数：循环节是从小数点后第一位开始循环的小数。

        • 混循环小数：循环节不是从小数点后第一位开始循环的小数。

        循环小数属于有理数，而任意一个有理数都有分数形式，本题的任务就是将一个循环小数转换为分数形式。

        为了方便表示，我们设该循环小数为n。

        根据题目的描述，我们能获取到的信息有以下两点。

        （1）n 的小数点后有q位数字。

        （2）n 的循环节是小数点后第p位到第q位。

         那么，要怎么将n转换为分数形式呢? 考虑以下两种情况。

         （1）n 为纯循环小数。

         （2）n 为混循环小数。

1. 情况 1

        我们假设n的循环节为a、分数形式为 ，即n=0.aaaaa...=  （a,x,y 均为整数）。

         即为我们所要求的答案。于是，我们可以从等式 n =  入手。

        等号的左边是个循环小数。显然，对于一个循环小数而言，要想将其转换为分数形式是 十分困难的。但是，对于一个整数而言，我们就能轻而易举地将其转换为分数。

         因此，我们需要尝试将等号的左边转换为整数来处理。

        怎么将等号的左边——一个循环小数转换为整数呢?

        简单来说，只要将其小数部分删除（减去小数部分），保留整数部分即可。

        由于n小于1，所以n的小数部分就是它本身，因此删除n的小数部分就相当于令n 减去它本身，这并没有什么意义。那么，不妨让我们来充分发挥n作为循环小数的性质。

         假设 n 的循环节 a 是一个 2 位数（即 ⌊lg(a)⌋+1 = 2，⌊⌋ 表示向下取整），那么 n× =a.aaaaa...，整数部分为 a，小数部分为 0.aaaaa...。

        和n一样，0.aaaaa... 是一个以 a 为循环节的小于1的循环小数(0.aaaaa...=n)，所 以有

n × 100 = a + n.

        移项得

        n = 

        解得         

        x =a, y =99.

提示如下：

2. 情况 2 

参考代码如下 

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

四、等差数列

【问题描述】

         数学老师给小明出了一道等差数列求和的题目。但是粗心的小明忘记了一部分的数列，只记得其中N个整数。

        现在给出这N个整数，小明想知道包含这N个整数的最短的等差数列有几项。

【输入格式】

        输入的第一行包含一个整数N。

        第二行包含N个整数A1,A2,...,AN。(注意A1∼AN并不一定是按等差数列中的 顺序给出)。

        其中，2⩽N⩽，0⩽Ai⩽。

【输出格式】

        输出一个整数表示答案。

【样例输入】

        

【样例输出】

        10

【样例说明】

         包含2,6,4,10,20 的最短的等差数列是 2,4,6,8,10,12,14,16, 18,20。

解析：

        题意是给定n个数A1,A2,...,An，要求构造出一个长度最短（项数最少的）的等差数列，使得该等差数列包含了这n个数，问最短长度（最少项数）为多少。

        既然和等差数列相关，那我们就尝试从等差数列的性质入手。

        我们知道，一个等差数列必然是有序的，但题目给定的n个数不一定是有序的，因此，我们需要将这n个数排序。

        等差数列相邻两项的差值均为一个常数，这个常数我们称之为公差。

        公差是等差数列中十分重要的一个概念。假设我们要构造的等差数列的公差为d，那么 对于该等差数列而言，从第二项开始，每一项的值都会等于前一项的值+d。因此，我们可推 断出该等差数列任意一项的值必定可由首项的值加上若干个d得到，即要使A1,A2,...,An 均被等差数列包含，则须满足这n个数中的每一个数都可由首项的值加上若干个d得到。

        那首项的值取多少合适呢?

        取A1 最为合适。

        因为如果A1不是首项，那么即使去除了A1前面的数，剩余的数所构成的数列依然会是 包含A1,A2,...,An 的等差数列。因此，要使等差数列的长度最短，取A1 为首项最为合适。 同理，等差数列末项的值取An最为合适，如下图所示。

        在确定了首项（A1）和末项（An）的取值后，我们就可以根据公式：项数=[(末项An − 首项A1)/ 公差d] +1 来得到答案。 

        显然，公差d越大，项数就越小。因此，d越大越好。

        不过d存在一个限制条件，即A1,A2,...,An中的每一个数都必须可由A1加上若干个 数得到。换言之，A2,A3,...,An中的每一个数与A1的差值都必须是d的倍数。

         如果用c2,c3,...,cn分别表示A2,A3,...,An与A1的差值，那么我们的任务就是要找 出最大的d，使得d是c2,c3,...,cn中每一个数的约数。

         到这步不难发现，我们要找的d其实就是c2,c3,...,cn的最大公约数。

         于是我们有d=gcd(c2,c3,...,cn)。

         在求出了d后，可得答案（项数）ans=  +1。

参考代码如下【时间复杂度为O(nlogn)】

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

五、最大比例

例题源自：2016年省赛-程序设计题 C/C++A组第10题；C/C++B组第10题

【问题描述】

        X星球的某个大奖赛设了M级奖励。每个级别的奖金是一个正整数。

        并且，相邻的两个级别间的比例是个固定值。

        也就是说，所有级别的奖金数构成了一个等比数列，比如：16,24,36,54，其等比值为 。 现在，我们随机调查了一些获奖者的奖金数。

        请你据此推算可能的最大的公比值。

【输入格式】

        第一行为数字

【输出格式】

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

【样例输入1】

        

【样例输出1】

        25/4

【样例输入2】

        

【样例输出2】

        5/2

这题自己看吧，我相信你们，代码如下：：

#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); // 更相减损术总是大减小（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]);// 将 a[i]/a[i-1] 化为最简分数后分别存储在 u[cnt] 和 d[cnt] 里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;
}

别忘了请点个赞+收藏+关注支持一下博主喵！！！！

关注博主，更多蓝桥杯nice题目静待更新:)