好啦,之前我们学了数论的一个基础概念:质数,同时也学了一些与质数相关的基本操作的算法实现方法,那么今天我们就来学一下数论的另一个基础概念:约数。 当然,约数的运用和质数还是有许许多多牵连的,所以还不会质数的小伙伴,可以先去康康这个鸭qwq 关于可爱的质数的基础合集 那么接下来,就让我们一起来看看,什么是约数,而它又有一些怎样的神奇操作把!
约数的概念应该不会有人忘记吧,和质数一样,也是小学就学过的概念,而且时时刻刻穿插在我们的数学学习生活中,比起质数运用的频率要高了许多,也更不容易忘记,不过为了内容的完整性还是写一下吧QwQ 对于一个整数N,如果有一个整数d可以将N整除,则d就是N的一个约数,也称N的因数。 好了,这就是约数的概念啦。那么接下来我们了解约数,和了解质数一样,从最最简单的操作开始。
想要了解约数,那就得先找到约数。那么对于给定的任意一个数n,我们应该怎么找到它的约数呢?嘿嘿,相信康到标题的小可爱都已经知道了。 没错!!!又是试除法,它又双叒叕来了!!! 思路大家应该都懂的吧,从1到n进行枚举,能与n整除的数就是n的约数。 不过同样的,如果在不优化的情况下,我们这样寻找质数的时间复杂度是O(n)的,我们同样可以用优化查质数的思路把它的时间复杂度优化成O(sqrt(n)),优化的思路我在质数的时候都写过了,这里就直接来康康优化过后的代码吧。
vector<int> found(int n) { vector<int> res; for(int i = 1; i <= n / i; i ++) { if(n % i == 0) res.push_back(i); if(n / i != i) res.push_back(n / i); // 这里防止重复加 } return res; }这个板子的思路并不难,也就不放题目了,我们直接下一个QwQ
随意给定一个数N,我们如何快速的求出约数的个数呢? 当然,我们用上面的那个方法是一定可以求出来的。但是,我们只用求出约数的个数耶,好似不用一个一个来算呀,那么有没有什么好的办法,比如有没有啥公式可以一步算出来呢? 答案是。。。当然有的! 我们已经知道了,对于任意一个数N,我们可以写成N = p1 ^ a1 * p2 ^ a2 * … . * pk ^ ak 的形式,那么,N的约数个数T = (a1 + 1) * (a2 + 1) * … * (ak + 1) 那么这个公式是怎么来的呢?我们假设N有一个约数W, 那么对于W,我们一定有W = p1 ^ b1 * p2 ^ b2 * … * pk ^ bk,对于bi,它的取值范围一定是0 <= bi <= ai。 这就变成了排列组合的问题,对于每一个质数pi,它的指数都有0到ai这(ai + 1)种选择,所以这个数总的约数格式也就是每个质数的指数的选择个数的乘积,也就是上面的公式。 我们来一起康康代码的实现吧QwQ
int num(int n) { unordered_map<int, int> hash; for(int i = 2; i <= n; i ++) { while(n % i == 0) { hash[i] ++; n /= i; } } if(n > 1) hash[n] ++; int res = 1; for(auto x : hash) { res = res * (x.second + 1); } return res; }这道题的思路其实还是有一点点复杂,所以我们来一道题目康一下吧。
约数个数 给定n个正整数aiai,请你输出这些数的乘积的约数个数,答案对109+7109+7取模。 输入格式 第一行包含整数n。 接下来n行,每行包含一个整数aiai。 输出格式 输出一个整数,表示所给正整数的乘积的约数个数,答案需对109+7109+7取模。 数据范围 1≤n≤1001≤n≤100, 1≤ai≤2∗1091≤ai≤2∗109 输入样例: 3 2 6 8
输出样例: 12
AC代码
#include<bits/stdc++.h> using namespace std; const int mod = 1e9 + 7; int main() { int T, n; cin >> T; unordered_map<int, int> hash; while(T --) { cin >> n; for(int i = 2; i <= n / i; i ++) { while(n % i == 0) { n /= i; hash[i] ++; } } if(n > 1) hash[n] ++; } long long ans = 1; for(auto t : hash) { ans = ans * (t.second + 1) % mod; } cout << ans << endl; return 0; }和约数的个数一样,约数的和同样也有自己的公式。 我们假设一个数N,它的约数的和为sum,我们可以得到公式sum = (p1 ^ 0 + p1 ^ 1 + … + p1 ^ a1) * (p2 ^ 0 + p2 ^ 1 + … + p2 ^ a2) … (pk ^ 0 + pk ^ 1 + … + pk ^ ak) 那么这个公式是怎么得来的呢?在约数的个数中,我们已经提到过了,N的任意一个约数W,都可以写成W = p1 ^ b1 p2 ^ b2 * … * pk ^ bk的形式,而且每个bi的取值范围都是0到ai的,所以当把所有约数相加时,每种指数搭配的情况都会不重复的出现一次,其实也就是我们给出的公式的展开式。 我们来一起康康模板
int sum(int n) { unordered_map<int, int> hash; for(int i = 2; i <= n / i; i ++) { while(n % i == 0) { hash[i] ++; n /= i; } } if(n > 1) hash[n] ++; int res = 1; for(auto x : hash) { int p = x.first, a = x.second; int temp = 1; while(a --) temp = temp * p + 1; res = res * temp; } return res; }同样的,看完模板,我们一起看道题目吧
约数的和 给定n个正整数aiai,请你输出这些数的乘积的约数之和,答案对109+7109+7取模。 输入格式 第一行包含整数n。 接下来n行,每行包含一个整数aiai。 输出格式 输出一个整数,表示所给正整数的乘积的约数之和,答案需对109+7109+7取模。 数据范围 1≤n≤1001≤n≤100, 1≤ai≤2∗1091≤ai≤2∗109 输入样例: 3 2 6 8
输出样例: 252
AC代码
#include<bits/stdc++.h> using namespace std; const int mod = 1e9 + 7; int main() { int T, n; cin >> T; unordered_map<int, int> hash; while(T --) { cin >> n; for(int i = 2; i <= n / i; i ++) { while(n % i == 0) { hash[i] ++; n /= i; } } if(n > 1) hash[n] ++; } long long ans = 1; for(auto t : hash) { int p = t.first, a = t.second; long long res = 1; while(a --) res = (res * p + 1) % mod; ans = ans * res % mod; } cout << ans << endl; return 0; }好啦,这是我们约数的最后一部分内容了,最大公约数,相信许多小伙伴也是早就已经知道这样一个概念了,但是我们在这里还是稍稍提一下下。给定两个任意的整数a和b,如果他们能同时被c整除,则称c为a和b的公约数,若c是最大的能同时整除a,b的数,则我们称c为a,b的最大公约数。 所以接下来,我们要解决掉问题,也就是怎么快速的找到两个数的最大公约数。
欧几里得算法,其实在我们的高中数学课本中已经出现过了。不过它的名字更加形象粗暴一点:辗转相除法。 嘿嘿,欧几里得算法你可能不认识,但是说辗转相除法,应该大多数小可爱是有影响的吧。 欧几里得算法的实现基础是:对于任意整数a和b,我们都可以得到a和b的最大公约数,与b和a%b的最大公约数相等。 那么,我们怎么退出这个规律的呢?我们首先得了解一些特殊的性质。我们可以很容易的想通,如果you 一个数d,满足d | a 并且d | b,则可以得出d | x * a + y * b。而a%b的值,我们可以通过化简得到a%b = a - a / b(向下取整) * b,我们把 - a / b 看成b的系数,结合上面的性质,就可以得出如果d | a 且 d | b,则d | a % b,我们取出d的可能值中的最大值,也就是a和b的最大公约数。 算法的模板也非常的简单,一行代码就搞定了。
int gcd(int a, int b) { return b ? gcd(b, a % b): a; }如果实在很不理解原理,直接记住代码其实也蛮好,毕竟简单过头了,这里也就不给例题了QwQ
好啦,这就是数论约数的部分基础内容了,和质数一样,在更深入的问题中会有不同的应用,如果碰到有趣的,我还是会单独重新整理。