前言

蓝桥杯官网：蓝桥杯大赛——全国大学生TMT行业赛事
✨本博客讲解 蓝桥杯C/C++ 备赛所涉及算法知识，此博客为第十四讲：数论【例题】

本篇博客所包含习题有：
👊等差数列
👊X的因子链
👊五指山

数论【习题】见博客：蓝桥杯第十四讲–数论【习题】

博客内容以题代讲，通过讲解题目的做法来帮助读者快速理解算法内容，需要注意：学习算法不能光过脑，更要实践，请读者务必自己敲写一遍本博客相关代码！！！

等差数列

来源： 第十届蓝桥杯省赛C++B/C组,第十届蓝桥杯省赛JAVAC组

题目要求

题目描述：

数学老师给小明出了一道等差数列求和的题目。

但是粗心的小明忘记了一部分的数列，只记得其中 $N$ 个整数。

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

输入格式：

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

第二行包含 $N$ 个整数 $A_1,A_2,\cdot \cdot \cdot ,A_N$。(注意 $A_1$∼$A_N$ 并不一定是按等差数列中的顺序给出)

输出格式：

输出一个整数表示答案。

数据范围：

$2\le N\le 100000,$
$0\le A_i\le 10^9$

输入样例：

5
2 6 4 10 20

  
 

  
1
  
2
 

输出样例：

10

  
 

  
1
 

样例解释：
包含 $2、6、4、10、20$ 的最短的等差数列是 $2、4、6、8、10、12、14、16、18、20$。

思路分析

每一项与第一项的差一定是 $d$ （$d$ 就是公差）的倍数
当 d != 0 时， $(a末-a初)/d+1$ ---- 让公差 $d$ 最大即可
当 d == 0 时，答案为 $n$

代码

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010;

int a[N];

int gcd(int a, int b)
{
    return b ? gcd(b, a % b) : a;
}

int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]);
    sort(a, a + n);

    int d = 0;
    for (int i = 1; i < n; i ++ ) d = gcd(d, a[i] - a[0]);

    if (!d) printf("%d\n", n);
    else printf("%d\n", (a[n - 1] - a[0]) / d + 1);

    return 0;
}

  
 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
 

X的因子链

题目要求

题目描述：

输入正整数 $X$，求 $X$ 的大于 $1$ 的因子组成的满足任意前一项都能整除后一项的严格递增序列的最大长度，以及满足最大长度的序列的个数。

输入格式：

输入包含多组数据，每组数据占一行，包含一个正整数表示 $X$。

输出格式：

对于每组数据，输出序列的最大长度以及满足最大长度的序列的个数。

每个结果占一行。

数据范围：

$1\le X\le 2^{20}$

输入样例：

2
3
4
10
100

  
 

  
1
  
2
  
3
  
4
  
5
 

输出样例：

1 1
1 1
2 1
2 2
4 6

  
 

  
1
  
2
  
3
  
4
  
5
 

思路分析

本题用到了 线性筛法筛质因数，这里不进行赘述，代码如下，详细原理可以参考博客：数学知识：质数

void get_primes(int n)
{
   for (int i = 2; i <= n; i ++ )
   {
       if (!st[i])
       {
           minp[i] = i;
           primes[cnt ++ ] = i;
       }
       for (int j = 0; primes[j] * i <= n; j ++ )
       {
           int t = primes[j] * i;
           st[t] = true;
           minp[t] = primes[j];
           if (i % primes[j] == 0) break;
       }
   }
}

  
 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
 

算术基本定理： 所有的正整数都可以唯一的分成若干个质因子乘积的形式，即：

$X=P_1^{{\alpha }_1}+P_2^{{\alpha }_2}+...+P_k^{{\alpha }_k}$

其中 $P_1,P_2,...,P_k$ 都是质因数，故对于一个整数 $X$，它一共有 ${\alpha }_1+{\alpha }_2+...+{\alpha }_k$ 个质因子，所以题目要求的序列最大长度就是：${\alpha }_1+{\alpha }_2+...+{\alpha }_k$，对应的个数为：$\frac{({\alpha }_1+{\alpha }_2+...+{\alpha }_k)!}{{\alpha }_1!\times {\alpha }_2!\times ...\times {\alpha }_k!}$

代码

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = (1 << 20) + 10;

int primes[N], cnt;
int minp[N];
bool st[N];

void get_primes(int n)
{
    for (int i = 2; i <= n; i ++ )
    {
        if (!st[i])
        {
            minp[i] = i;
            primes[cnt ++ ] = i;
        }
        for (int j = 0; primes[j] * i <= n; j ++ )
        {
            int t = primes[j] * i;
            st[t] = true;
            minp[t] = primes[j];
            if (i % primes[j] == 0) break;
        }
    }
}

int main()
{
    get_primes(N - 1);

    int fact[30], sum[N];

    int x;
    while (scanf("%d", &x) != -1)
    {
        int k = 0, tot = 0;
        while (x > 1)
        {
            int p = minp[x];
            fact[k] = p, sum[k] = 0;
            while (x % p == 0)
            {
                x /= p;
                sum[k] ++ ;
                tot ++ ;
            }
            k ++ ;
        }

        LL res = 1;
        for (int i = 1; i <= tot; i ++ ) res *= i;
        for (int i = 0; i < k; i ++ )
            for (int j = 1; j <= sum[i]; j ++ )
                res /= j;

        printf("%d %lld\n", tot, res);
    }

    return 0;
}

  
 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
  
43
  
44
  
45
  
46
  
47
  
48
  
49
  
50
  
51
  
52
  
53
  
54
  
55
  
56
  
57
  
58
  
59
  
60
  
61
  
62
  
63
  
64
  
65
  
66
  
67
  
68
 

五指山

题目要求

题目描述：

大圣在佛祖的手掌中。

我们假设佛祖的手掌是一个圆圈，圆圈的长为 $n$，逆时针记为：$0,1,2,\dots ,n-1$，而大圣每次飞的距离为 $d$。

现在大圣所在的位置记为 $x$，而大圣想去的地方在 $y$。

要你告诉大圣至少要飞多少次才能到达目的地。

注意： 孙悟空的筋斗云只沿着逆时针方向翻。

输入格式：

有多组测试数据。

第一行是一个正整数 $T$，表示测试数据的组数；

每组测试数据包括一行，四个非负整数，分别为如来手掌圆圈的长度 $n$，筋斗所能飞的距离 $d$，大圣的初始位置 $x$ 和大圣想去的地方 $y$。

输出格式：

对于每组测试数据，输出一行，给出大圣最少要翻多少个筋斗云才能到达目的地。

如果无论翻多少个筋斗云也不能到达，输出 $Impossible$。

数据范围：

$2<n<10^9,$
$0<d<n,$
$0\le x,y<n$

输入样例：

2
3 2 0 2
3 2 0 1

  
 

  
1
  
2
  
3
 

输出样例：

1
2

  
 

  
1
  
2
 

思路分析

本题用到了 扩展欧几里得算法，具体原理可见博客：数学知识：扩展欧几里得算法

由题目可以抽象出数学模型如下：

$x+pd=y(modn)$
$x+pd=y+qn$
$-qn+pd=y-x$ 即形式为 $qn+pd=y-x------方程1$

由于 $n,d,y,x$ 都为常数,以及 $q,p$ 均为变量我们很容易联想到扩展欧几里得算法 $ax+by=d------方程2$
但我们题目要求的和扩展欧几里得算法右边的有些不同,扩展欧几里得算法右边的为最大公约数,我们题目给出的 $y-x$ 未必
是 $n$ 和 $d$ 的最大公约数,当思考后我们发现,如果 $d$ 不能整除 $y-x$ 则无解.我们可以先用扩展欧几里得算法求出 $n$ 和 $d$ 的最大公约
数,然后将 $方程2$ 乘以 $(y-x)/d$ 即可转化为 $方程1$,我们观察题目发现题目要求的是最小的 $p$ 值,那如何求呢？

由扩展欧几里得解得结论我们可以得到： $p=p0+kn/d,p$ 最小为 $p0,p0$ 即是我们题目要求的最小值

代码

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

LL exgcd(LL a, LL b, LL &x, LL &y)
{
    if (!b)
    {
        x = 1, y = 0;
        return a;
    }
    LL d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}

int main()
{
    int T;
    scanf("%d", &T);
    while (T -- )
    {
        LL n, d, x, y, a, b;
        scanf("%lld%lld%lld%lld", &n, &d, &x, &y);

        int gcd = exgcd(n, d, a, b);
        if ((y - x) % gcd) puts("Impossible");
        else
        {
            b *= (y - x) / gcd;
            n /= gcd;
            printf("%lld\n", (b % n + n) % n);
        }
    }

    return 0;
}

  
 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
 

文章来源: chen-ac.blog.csdn.net，作者：辰chen，版权归原作者所有，如需转载，请联系作者。

原文链接：chen-ac.blog.csdn.net/article/details/122794038