文章目录
前言
一、约数是什么
二、三大模板
1、试除法求约数个数
2、求约数个数
3、求约数之和
三、真题演练
前言
约数和质数一样在蓝桥杯考试中是在数论中考察频率较高的一种,在省赛考察的时候往往就是模板题,难度大一点会结合其他知识点考察,但是仍然会用到模板,这里有三大模板,第一个是试除法求约数个数,第二个是求约数个数,第三个是求约数的和(来自y总的三个模型)
一、约数是什么
约数(约数的含义是什么) 1、意思 1.大约的数目。 2.一个数能够整除另一数,这个数就是另一数的约数。如2,3,4,6都能整除12,因此2,3,4,6都是12的约数。也叫因数。最后俩个都插到这个动态数组中,但是注意
二、三大模板
1、试除法求约数个数
算法思想:算x的约数,对 小于等于x的根号数求约数,当你求得一个约数,对应的也有另一个数是约数,就比如算12的约数,当算出3是约数,可得 4(12/ 3)也是12的约数。但是注意如果16的约数4对应的约数还是4不能在被放进去,所以要加一个特判
代码
- #include <iostream>
- #include <cstring>
- #include <algorithm>
- #include <vector>
-
- using namespace std;
-
- vector<int> get_divisors(int n)
- {
- vector <int> res;
- for(int i = 1;i <= n / i; i ++)
- {
- if(n % i == 0){
- res.push_back(i);
- if(i != n / i) res.push_back(n/i);
- }
- }
- sort(res.begin(),res.end());
- return res;
- }
- int main()
- {
- int n;
- cin >> n;
- while(n --)
- {
- int x;
- cin >> x;
- vector <int> res;
- res = get_divisors(x);
- for(auto c : res)
- {
- cout << c << " ";
- }
- cout << endl;
-
-
- }
- }
2、求约数个数
如果有一个数n,且 n = p1^c1 * p2 ^ c2 * p3 ^c3 + ...... + pn^cn;
那么它的约数个数和就等于 (c1 + 1 ) * ( c2 + 1 ) * (c3 + 1 ) ....(cn + 1);
p1^c1,这样的数就是上文中所介绍的质因数,通过求质因数,在求c1 + 1的值即可。
题目·
代码
- #include <iostream>
- #include <cstring>
- #include <algorithm>
- #include <unordered_map>
- const int mod = 1e9 + 7;
- typedef long long LL;
- using namespace std;
- int main()
- {
- unordered_map <int,int> primes;
- int n;
- cin >> n;
- while (n -- )
- {
- int x;
- cin >> x;
- for(int i = 2;i <= x / i;i ++)
- {
- while(x % i == 0)
- {
- x /= i;
- primes[i] ++;
- }
-
- }
- if(x > 1) primes[x] ++;
- }
-
- LL res = 1;
- for(auto c: primes)
- {
- res = res * (c.second + 1) % mod;
- }
- cout << res << endl;
- }
3、求约数之和
如果有一个数n,且 n = p1^c1 * p2 ^ c2 * p3 ^c3 + ...... + pn^cn;
那么它的约数之和为(p1^0 + p2^1 + p3 ^3 + .. +p^c1) * ... *( pn^c1 + pn^c2 +pn^c3 + ...+ pn^cn)
求解方法和上面一样,先是解出质因数,然后求出约数和的过程很巧妙,看下面代码
题目
题解
- #include <bits/stdc++.h>
- typedef long long LL;
- const int mod = 1e9 + 7;
- using namespace std;
- int main()
- {
- unordered_map<int,int> primes; //一个值存的是这个质因数,第二个存的是指数
- int n;
- cin >>n;
- while (n -- )
- {
- int x;
- cin >> x;
- for(int i = 2;i <= x / i;i ++)
- {
- while(x % i == 0)
- {
- x /= i;
- primes[i] ++ ; // 指数加一
- }
-
- }
- if(x > 1) primes[x] ++;
- }
- LL res = 1;
- for(auto c : primes)
- {
- int a = c.first,b = c.second;
- LL t = 1;
- while(b--) t = (t * a + 1) % mod;
- res = res * t % mod;
- }
- cout << res << endl;
- }
最后一步为什么会用这个t ,假设开始时为
t : 1
t :p+ 1 (t = 1 *p + 1)
t : p^2 + p +1 ( t = (p+1) * p +1 )\
....
最后t : t=p^b+p^b−1+…+1
四、求最大公约数
求最大公约数,要用到欧几里得算法,就是 gcd (a,b) = gcd(b,a%b),注意b为0的时候按照欧几里得算法,b等于0,取a;
题目
代码
- #include <iostream>
- #include <cstring>
- #include <algorithm>
-
- using namespace std;
- int gcd(int a,int b)
- {
- return b ? gcd(b,a%b):a ; //b为0的时候按照欧几里得算法,b等于0,取a
- }
-
- int main()
- {
- int n;
- cin >> n;
- while(n --)
- {
- int a,b;
- cin >> a >> b;
- int t =gcd(a,b);
- cout << t <<endl;
- }
- }
三、真题演练
2020填空题
题目
题目描述
本题为填空题,只需要算出结果后,在代码中使用输出语句将所填结果输出即可。
12000001200000 有多少个约数(只计算正约数)。
运行限制
- 最大运行时间:1s
- 最大运行内存: 128M
代码
- #include <iostream>
- #include <cstring>
- #include <algorithm>
- #include <unordered_map>
- const int mod = 1e9 + 7;
- typedef long long LL;
- using namespace std;
- int main()
- {
- unordered_map <int,int> primes;
-
- int x;
- x = 1200000;
- for(int i = 2;i <= x / i;i ++)
- {
- while(x % i == 0)
- {
- x /= i;
- primes[i] ++;
- }
-
- }
- if(x > 1) primes[x] ++;
-
- LL res = 1;
- for(auto c: primes)
- {
- res = res * (c.second + 1) % mod;
- }
- cout << res << endl;
- }