前言
✨本博客讲解 蓝桥杯C/C++ 备赛所涉及算法知识，此博客为第十四讲：数论【例题】
本篇博客所包含习题有：
👊等差数列
👊X的因子链
👊五指山
数论【习题】见博客：蓝桥杯第十四讲–数论【习题】
博客内容以题代讲，通过讲解题目的做法来帮助读者快速理解算法内容，需要注意：学习算法不能光过脑，更要实践，请读者务必自己敲写一遍本博客相关代码！！！
等差数列
来源： 第十届蓝桥杯省赛C++B/C组,第十届蓝桥杯省赛JAVAC组
题目要求
题目描述：
数学老师给小明出了一道等差数列求和的题目。
但是粗心的小明忘记了一部分的数列，只记得其中 N 个整数。
现在给出这 N 个整数，小明想知道包含这 N 个整数的最短的等差数列有几项？
输入格式：
输出格式：
输出一个整数表示答案。
数据范围：
输入样例：
5 2 6 4 10 20
输出样例：
10
样例解释：
包含 2 、 6 、 4 、 10 、 20 的最短的等差数列是 2 、 4 、 6 、 8 、 10 、 12 、 14 、 16 、 18 、 20。
思路分析
代码
#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; }
X的因子链
题目要求
题目描述：
输入正整数 X ，求 X 的大于 1 的因子组成的满足任意前一项都能整除后一项的严格递增序列的最大长度，以及满足最大长度的序列的个数。
输入格式：
输入包含多组数据，每组数据占一行，包含一个正整数表示 X 。
输出格式：
对于每组数据，输出序列的最大长度以及满足最大长度的序列的个数。
每个结果占一行。
数据范围：
1≤X≤220
输入样例：
2 3 4 10 100
输出样例：
1 1 1 1 2 1 2 2 4 6
思路分析
本题用到了 线性筛法筛质因数，这里不进行赘述，代码如下，详细原理可以参考博客：数学知识：质数
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; } } }
算术基本定理： 所有的正整数都可以唯一的分成若干个质因子乘积的形式，即：
代码
#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; }
五指山
题目要求
题目描述：
大圣在佛祖的手掌中。
我们假设佛祖的手掌是一个圆圈，圆圈的长为 n，逆时针记为：0 , 1 , 2 , … , n − 1 ，而大圣每次飞的距离为 d 。
现在大圣所在的位置记为 x，而大圣想去的地方在 y 。
要你告诉大圣至少要飞多少次才能到达目的地。
注意： 孙悟空的筋斗云只沿着逆时针方向翻。
输入格式：
有多组测试数据。
第一行是一个正整数 T ，表示测试数据的组数；
每组测试数据包括一行，四个非负整数，分别为如来手掌圆圈的长度 n ，筋斗所能飞的距离 d ，大圣的初始位置 x 和大圣想去的地方 y。
输出格式：
对于每组测试数据，输出一行，给出大圣最少要翻多少个筋斗云才能到达目的地。
如果无论翻多少个筋斗云也不能到达，输出Impossible。
数据范围：
输入样例：
2 3 2 0 2 3 2 0 1
输出样例：
1 2
思路分析
本题用到了 扩展欧几里得算法，具体原理可见博客：数学知识：扩展欧几里得算法
由题目可以抽象出数学模型如下：
代码
#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; }
