当前位置：首页 > article >正文

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

article 2024/11/18 8:38:40

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

关注博主，更多蓝桥杯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. 解释

质因数分解：
- 将 nn 分解为若干个质数的乘积，每个质数的指数表示该质数在分解中的次数。
约数个数公式：
- 每个质数 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 的幂次， $\prod$ 表示连乘符号。

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

对于5!，其值为1×2×3×4×5=120，其质因子有2,3,5，对应的幂次分别为3,1,1，即 120 = $2^{3}$ × $3^{1}$ × $5^{1}$ 。如果我们对 2,3,4,5 分别做质因数分解，则 2 = $2^{1}$ ，3 = $3^{1}$ ，4 = $2^{2}$ ，5 = $5^{1}$ 。不难发现，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 的幂次， $\prod$ 表示连乘符号。

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

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

因为n的定义是约数个数为100的最小整数，即n⩽x→n⩽ $2^{4}$ × $3^{4}$ × $5^{3}$ →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∼ $10^{6}$ 内每个数的因子个数，会发现其中因子数最多的也只有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）大小不超过 $10^{18}$ 。

（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 <= INF
                if (j * (k + 1) > 1000 || INF / prime[i] < p) break;
                if (k > 0) p *= prime[i]; // 第 k 轮循环时，p = prime[i]^k
                if (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。

【输出格式】

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

【样例输入】

【样例输出】

解析：

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

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

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

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

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

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

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

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

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

（1）n 为纯循环小数。

（2）n 为混循环小数。

1. 情况 1

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

$\frac{x}{y}$ 即为我们所要求的答案。于是，我们可以从等式 n = $\frac{x}{y}$ 入手。

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

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

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

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

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

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

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

n × 100 = a + n.

移项得

n = $\frac{a}{99}$

解得

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⩽ $10^{5}$ ，0⩽Ai⩽ $10^{9}$ 。

【输出格式】

输出一个整数表示答案。

【样例输入】

【样例输出】

【样例说明】

包含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= $\frac{An - A1}{d}$ +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，其等比值为 $\frac{3}{2}$ 。现在，我们随机调查了一些获奖者的奖金数。

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

【输入格式】

第一行为数字

【输出格式】

一个形如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题目静待更新:)

查看全文

http://www.kler.cn/a/398455.html