如何在网站上添加备案号,爱站网 关键词挖掘工具站长工具,商城在线,化妆品网站制作需要别忘了请点个赞收藏关注支持一下博主喵#xff01;#xff01;#xff01;!
关注博主#xff0c;更多蓝桥杯nice题目静待更新:) 简单数论
一、阶乘约数
【问题描述】 定义阶乘n!123...n。 请问100! #xff08;100 的阶乘#xff09;有多少个正约数。
【答案提交】 这…
别忘了请点个赞收藏关注支持一下博主喵!
关注博主更多蓝桥杯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使得
np1e1×p2e2×⋯×pkeknp1e1×p2e2×⋯×pkek
其中 p1,p2,…,pkp1,p2,…,pk 是互不相同的质数e1,e2,…,eke1,e2,…,ek 是正整数。
例如考虑数字 60 6022×31×516022×31×51
2. 约数定理Divisor Function
约数定理 是基于唯一分解定理的一个推论它提供了计算一个数的所有正约数个数的方法。具体来说
如果一个正整数 nn 的质因数分解为 np1e1×p2e2×⋯×pkeknp1e1×p2e2×⋯×pkek
那么 nn 的所有正约数的个数 d(n)d(n) 可以通过以下公式计算 d(n)(e11)×(e21)×⋯×(ek1)d(n)(e11)×(e21)×⋯×(ek1)
3. 解释 质因数分解 将 nn 分解为若干个质数的乘积每个质数的指数表示该质数在分解中的次数。 约数个数公式 每个质数 pipi 的指数 eiei 可以取 0 到 eiei 之间的任意值共有 ei1ei1 种选择。因此所有质数的选择组合起来总共有 (e11)×(e21)×⋯×(ek1)(e11)×(e21)×⋯×(ek1) 种不同的组合方式这就是 nn 的所有正约数的个数。
4. 示例
考虑数字 60 6022×31×516022×31×51
根据约数定理 d(60)(21)×(11)×(11)3×2×212d(60)(21)×(11)×(11)3×2×212
验证 60 的所有正约数为1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60共 12 个。
5. 总结
唯一分解定理每个正整数可以唯一地表示为若干个质数的乘积。约数定理基于唯一分解定理提供了一个计算一个数的所有正约数个数的方法。
本题解析
这题我们将用到唯一分解定理和约数定理 题目要我们求的是100!的约数个数。约数即因子如果按照最简单的方法来做题我们会习惯性地先计算出100! 的值设该值为n再枚举1∼√n中的所有数以找出并统计n 的因子及因子个数具体代码见参考代码如下。
#include iostream
#include cmathint 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的整数nn可以分解质因数 其中pi 表示n的第i个质因子ai 表示pi 的幂次表示连乘符号。 根据约数定理可得n的正约数的个数为。所 i1 以我们只要求得100! 的每个质因子对应的幂次即可求出答案。但怎么求100! 的每个质因子 呢? 我们以5!为例简单演示一遍。 对于5!其值为1×2×3×4×5120其质因子有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,...。 现在小明想知道当t100时St是多少?即S100是多少?
【答案提交】 这是一道结果填空题你只需要算出结果后提交即可。本题的结果作为一个整数在 提交答案时只填写这个整数填写多余的内容将无法得分。
解析 为了追求简单我们可以先尝试用枚举法来搜寻答案。方法为从小到大枚举整数枚举 的同时判断当前枚举到的数是否能作为答案。 怎么判断一个数是否能作为答案呢?同样为了追求简单我们可以求出该数的所有因子 以统计因子的个数再判断因子数是否为100即可。 判断的结果有两种能和不能。 由于我们是从小到大枚举的所以如果判断的结果为能那么判断的数就一定会是最小 的、满足条件的答案结束枚举如果判断的结果为不能就继续枚举如下图所示。 显然这种简单的方法是一定能找到正确答案的但问题在于该方法找到答案所需要花 费的时间是不确定的可能需要1年也可能连1秒都不要。对此我们可以粗略分析一下。 假设本题的正确答案为n那么枚举和判断的总的时间复杂度就为O(n√n)。 • 根据唯一分解定理可得对于一个大于 1 的整数 nn 可以分解质因数 其中pi 表示n的第i个质因子ai 表示pi 的幂次表示连乘符号。 • 根据约数定理可得n的约数个数为。 有了这两个定理后我们就可以任取一个数来确定n的上限。假设我们取的数为x它 的值为××由约数定理可得x的约数个数为(41)×(41)×(31)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为例为了方便起见我们设S1000n即设n是约数个数为1000的最小整数。 那么根据唯一分解定理n 。。根据约数定理n 的约数个数为 (a11) (a2 1)...(ak 1)。 为了减少答案的搜寻范围我们先对答案的性质进行分析。 由于n的定义是约数个数为1000的最小整数所以为了保证n的值最小须满足a1⩾ a2 ⩾ ... ⩾ ak。 什么意思? 我们来试想一下如果数值小的质因子的幂次小于数值大的质因子的幂次那么只要 我们将两个质因子的幂次交换n的值就会变小而约数个数不会改变。
举例说明 因此可得数值越小的质因子对应的幂次一定越大即a1⩾a2⩾...⩾ak。 另外根据答案的值小于1018我们还可以再获得以下两条信息。 1n 的质因子个数最多为15。 2n 的质因子的最高幂次为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⩽15prime[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 30.1666...等于1 6。
【输入格式】 输入第一行包含两个整数p和q表示S的循环节是小数点后第p位到第q位。 第二行包含一个q位数代表S的小数部分前q位。 其中1⩽p⩽q⩽10。
【输出格式】 输出两个整数用一个空格分隔分别表示答案的分子和分母。
【样例输入】 【样例输出】 17
解析 在开始做题之前我们先来看看循环小数的定义一个数的小数部分从某一位起有一 个或多个数字依次重复出现循环节的无限小数叫循环小数。循环小数又分以下两种。 • 纯循环小数循环节是从小数点后第一位开始循环的小数。 • 混循环小数循环节不是从小数点后第一位开始循环的小数。 循环小数属于有理数而任意一个有理数都有分数形式本题的任务就是将一个循环小数转换为分数形式。 为了方便表示我们设该循环小数为n。 根据题目的描述我们能获取到的信息有以下两点。 1n 的小数点后有q位数字。 2n 的循环节是小数点后第p位到第q位。 那么要怎么将n转换为分数形式呢? 考虑以下两种情况。 1n 为纯循环小数。 2n 为混循环小数。
1. 情况 1 我们假设n的循环节为a、分数形式为 即n0.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) { // 情况1n 为纯循环小数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 { // 情况2n 为混循环小数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的最大公约数。 于是我们有dgcd(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/CA组第10题C/CB组第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题目静待更新:)
