算法刷题day43

本文主要是介绍算法刷题day43，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

引言

今天复习的是快速幂的剩余问题、质数、约数的问题，发现其实不难，都是在基础的模板上进行变化，但是不好想，基本自己是想不出来的，所以这种问题还是要事先做过之后才会做，所以得多刷题了，加油！

已知信息

在int范围内约数个数最多的有1600个，在 $10^9$ 范围内有1344个

一、公约数

标签：最大公约数、试除法、二分

思路：先求出所有 $a, b$ 的公约数，然后用二分找到最大的即可。求所有公约数，可以先求出最大公约数，然后对其进行分解约数即可，最后排个序。
在这里插入图片描述

题目描述：

给定两个正整数 a 和 b。你需要回答 q 个询问。每个询问给定两个整数 l,r，你需要找到最大的整数 x,满足：x 是 a 和 b 的公约数。l≤x≤r。输入格式
第一行包含两个整数 a,b。第二行包含一个整数 q。接下来 q 行，每行包含两个整数 l,r.输出格式
每个询问输出一行答案，即满足条件的最大的 x，如果询问无解，则输出 −1。数据范围
前六个测试点满足 1≤a,b≤100，1≤q≤20。
所有测试点满足 1≤a,b≤109，1≤q≤104，1≤l≤r≤109。输入样例：
9 27
3
1 5
10 11
9 11
输出样例：
3
-1
9

示例代码：

#include <bits/stdc++.h>using namespace std;typedef long long LL;
typedef pair<int,int> PII;
#define x first
#define y secondconst int N = 1350;int a, b, q;
int divisors[N], cnt;int gcd(int a, int b)
{return b ? gcd(b,a%b) : a;
}void init(int a, int b)
{int d = gcd(a,b);for(int i = 1; i <= d / i; ++i){if(d % i == 0){divisors[cnt++] = i;if(d / i != i) divisors[cnt++] = d / i;}}sort(divisors,divisors+cnt);
}int main()
{ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);cin >> a >> b >> q;init(a, b);while(q--){int x, y; cin >> x >> y;int res = -1;int l = 0, r = cnt - 1;while(l < r){int mid = (LL)l + r + 1 >> 1;if(divisors[mid] <= y) l = mid;else r = mid - 1;}if(divisors[r] >= x && divisors[r] <= y) res = divisors[r];cout << res << endl;}return 0;
}

二、序列的第k个数

标签：快速幂

思路：首先判断出是等比数列还是等差数列，然后再用等差数列公式和等比数列公式求出来就行了 $等差数列：a_k = a_1 + (k - 1) * d$ $等比数列：a_k = a_1 * d^{k-1}$

题目描述：

BSNY 在学等差数列和等比数列，当已知前三项时，就可以知道是等差数列还是等比数列。现在给你 整数 序列的前三项，这个序列要么是等差序列，要么是等比序列，你能求出第 k 项的值吗。如果第 k 项的值太大，对其取模 200907。输入格式
第一行一个整数 T，表示有 T 组测试数据；对于每组测试数据，输入前三项 a,b,c，然后输入 k。输出格式
对于每组数据，输出第 k 项取模 200907 的值。数据范围
1≤T≤100,1≤a≤b≤c≤109,1≤k≤109
输入样例：
2
1 2 3 5
1 2 4 5
输出样例：
5
16

示例代码：

#include <bits/stdc++.h>using namespace std;typedef long long LL;
typedef pair<int,int> PII;
#define x first
#define y secondconst int N = 1e5+10, MOD = 200907;int n, m;LL qmi(LL a, LL k)
{LL res = 1;while(k){if(k&1) res = res * a % MOD;k >>= 1;a = a * a % MOD;}return res;
}int main()
{ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);int T; cin >> T;while(T--){int a, b, c, k; cin >> a >> b >> c >> k;if(b - a == c - b)  //等差数列 {int d = b - a;LL res = ((LL)a % MOD + (LL)(k - 1) % MOD * d % MOD) % MOD;cout << res << endl;}else {int d = b / a;LL res = a * qmi(d,k-1) % MOD;cout << res << endl;}}return 0;
}

三、越狱

标签：快速幂、组合计数

思路：首先总共有 $m^n$ 种可能的结果，不发生越狱的情况为 $m * (m-1)^{n-1}$ 种可能，如下图：
在这里插入图片描述
所以发生越狱的可能情况为： $m^n - m * (m-1)^{n-1}$ ，用快速幂求解即可。

题目描述：

监狱有连续编号为 1 到 n 的 n 个房间，每个房间关押一个犯人。有 m 种宗教，每个犯人可能信仰其中一种。不存在没有信仰的犯人。如果相邻房间的犯人信仰的宗教相同，就可能发生越狱。求有多少种状态可能发生越狱。输入格式
共一行，包含两个整数 m 和 n。输出格式
可能越狱的状态数，对 100003 取余。数据范围
1≤m≤108,1≤n≤1012
输入样例：
2 3
输出样例：
6
样例解释
所有可能的 6 种状态为：(000)(001)(011)(100)(110)(111)。

示例代码：

#include <bits/stdc++.h>using namespace std;typedef long long LL;
typedef pair<int,int> PII;
#define x first
#define y secondconst int N = 1e5+10, MOD = 100003;LL m, n;LL qmi(LL a, LL k)
{LL res = 1;while(k){if(k&1) res = res * a % MOD;k >>= 1;a = a * a % MOD;}return res;
}int main()
{ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);cin >> m >> n;LL res = (qmi(m,n) - m * qmi(m-1,n-1) % MOD + MOD) % MOD;cout << res << endl;return 0;
}

四、等差数列

标签：数论、最大公约数

思路：先排个序，然后求出各项差之间的最大公约数，即就是 $d$ ，然后用公式 $\frac{a[n-1] - a[0]}{ d} + 1$ ，如果 $d$ 为 $0$ ，直接输出 $n$ 即可。

题目描述：

数学老师给小明出了一道等差数列求和的题目。但是粗心的小明忘记了一部分的数列，只记得其中 N 个整数。现在给出这 N 个整数，小明想知道包含这 N 个整数的最短的等差数列有几项？输入格式
输入的第一行包含一个整数 N。第二行包含 N 个整数 A1,A2,⋅⋅⋅,AN。(注意 A1∼AN 并不一定是按等差数列中的顺序给出)输出格式
输出一个整数表示答案。数据范围
2≤N≤100000,0≤Ai≤109
输入样例：
5
2 6 4 10 20
输出样例：
10
样例解释
包含 2、6、4、10、20 的最短的等差数列是 2、4、6、8、10、12、14、16、18、20。

示例代码：

#include <bits/stdc++.h>using namespace std;typedef long long LL;
typedef pair<int,int> PII;
#define x first
#define y secondconst int N = 1e5+10;int n;
int a[N];int main()
{ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);cin >> n;for(int i = 0; i < n; ++i) cin >> a[i];sort(a,a+n);int d = 0;for(int i = 1; i < n; ++i) d = gcd(a[i]-a[0],d);if(!d) cout << n << endl;else cout << ((a[n-1] - a[0]) / d + 1) << endl;return 0;
}

五、公约数

标签：数学知识、约数、试除法、因式分解

思路：用试除法操作即可，时间复杂度为 $\sqrt{N}$

题目描述：

输入 n 个整数，依次输出每个数的约数的个数。输入格式
第一行包含整数 n。第二行包含 n 个整数 ai。输出格式
共 n 行，按顺序每行输出一个给定整数的约数的个数。数据范围
1≤n≤1000,1≤ai≤109
输入样例：
5
1 3 4 6 12
输出样例：
1
2
3
4
6

示例代码：

#include <bits/stdc++.h>using namespace std;typedef long long LL;
typedef pair<int,int> PII;
#define x first
#define y secondconst int N = 1e5+10;int n;int get_divisors(int n)
{int res = 0;for(int i = 1; i <= n / i; ++i){if(n % i == 0){res++;if(n / i != i) res++;}}return res;
}int main()
{ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);cin >> n;while(n--){int t; cin >> t;cout << get_divisors(t) << endl;}return 0;
}

六、质因数个数

标签：数论、分解质因数

思路：就分解质因数即可。

题目描述：

给定正整数 n，请问有多少个质数是 n 的约数。输入格式
输入的第一行包含一个整数 n。输出格式
输出一个整数，表示 n 的质数约数个数。数据范围
对于 30% 的评测用例，1≤n≤10000。
对于 60% 的评测用例，1≤n≤109。
对于所有评测用例，1≤n≤1016。输入样例：
396
输出样例：
3
样例解释
396有 2,3,11 三个质数约数。

示例代码：

#include <bits/stdc++.h>using namespace std;typedef long long LL;
typedef pair<int,int> PII;
#define x first
#define y secondconst int N = 1e5+10;LL n;int main()
{ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);cin >> n;int res = 0;for(LL i = 2; i <= n / i; ++i){if(n % i == 0){res++;while(n % i == 0) n /= i;}}if(n > 1) res++;cout << res << endl;return 0;
}

七、完全平方数

标签：分解质因数

思路：由算数基本定理可知，每个数都是由其质因数组成的，那么一个数能被称为完全平方数，那么其每个质因数的次数都是偶数，那么要求一个 $x$ ，使得 $\cdot x$ 为一个完全平方数，那么将其每个质因数变为偶数即可，所以也就是对其分解质因数，个数为奇数加进答案里。

题目描述：

一个整数 a 是一个完全平方数，是指它是某一个整数的平方，即存在一个整数 b，使得 a=b2。给定一个正整数 n，请找到最小的正整数 x，使得它们的乘积是一个完全平方数。输入格式
输入一行包含一个正整数 n。输出格式
输出找到的最小的正整数 x。数据范围
对于 30% 的评测用例，1≤n≤1000，答案不超过 1000。
对于 60% 的评测用例，1≤n≤108，答案不超过 108。
对于所有评测用例，1≤n≤1012，答案不超过 1012。输入样例1：
12
输出样例1：
3
输入样例2：
15
输出样例2：
15

示例代码：

#include <bits/stdc++.h>using namespace std;typedef long long LL;
typedef pair<int,int> PII;
#define x first
#define y secondconst int N = 1e5+10;LL n;int main()
{ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);cin >> n;LL res = 1;for(int i = 2; i <= n / i; ++i){if(n % i == 0){int s = 0;while(n % i == 0) s++, n /= i;if(s % 2) res *= i;}}if(n > 1) res *= n;cout << res << endl;return 0;
}

八、阶乘分解

标签：数学知识、质数

思路：先求出 $1\sim n$ 的所有质数，用线性筛法即可。然后遍历每个质数出现了几次，可以用 $\lfloor\frac{n}{p}\rfloor + \lfloor\frac{n}{p^2}\rfloor +\ \cdots\ + \lfloor\frac{n}{p^k}\rfloor$ 求出来即可。

题目描述：

给定整数 N，试把阶乘 N! 分解质因数，按照算术基本定理的形式输出分解结果中的 pi 和 ci 即可。输入格式
一个整数 N。输出格式
N! 分解质因数后的结果，共若干行，每行一对 pi,ci，表示含有 pcii 项。按照 pi 从小到大的顺序输出。数据范围
3≤N≤106
输入样例：
5
输出样例：
2 3
3 1
5 1
样例解释
5!=120=23∗3∗5

示例代码：

#include <bits/stdc++.h>using namespace std;typedef long long LL;
typedef pair<int,int> PII;
#define x first
#define y secondconst int N = 1e6+10;int primes[N], cnt;
bool st[N];void get_primes(int n)
{for(int i = 2; i <= n; ++i){if(!st[i]) primes[cnt++] = i;for(int j = 0; primes[j] * i <= n; ++j){st[primes[j] * i] = true;if(i % primes[j] == 0) break;}}
}int main()
{ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);int n; cin >> n;get_primes(n);for(int i = 0; i < cnt; ++i){int p = primes[i];int s = 0;for(int j = n; j; j /= p) s += j / p;cout << p << " " << s << endl;}return 0;
}