算法模版：数论之约数全家桶-阿里云开发者社区

算法模版：数论之约数全家桶

2022-04-15 225

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 算法模版：数论之约数全家桶

前言

唤我沈七就好啦。

最大公约数

最大公约数，指两个或多个整数共有约数中最大的一个。a，b的最大公约数记为（a，b）

最大公约数可以为1。两个互为质数的数,其最大公约数就是1。如3和5的最大公约数就是1。

辗转相除法

求两个数的最大公约数的步骤如下:

333用小的一个数除大的一个数,得第一个余数;

再用第一个余数除小的一个数,得第二个余数;

又用第二个余数除第一个余数,得第三个余数;

这样逐次用后一个数去除前一个余数,直到余数是0为止.

最后一个除数就是所求的最大公约数。

例如求1515和600的最大公约数,

第一次:用600除1515,商2余315;

第二次:用315除600,商1余285;

第三次:用285除315,商1余30;

第四次:用30除285,商9余15;

第五次:用15除30,商2余0.

1515和600的最大公约数是15

实现代码

while(b)
  {
  r=a%b;
  sum+=a/b;
  a=b;b=r;
  }

欧几里得算法

欧几里得算法实际上是辗转相除法的递归实现版本，核心代码只有一行。

long long gcd(long long a,long long b)
{
  return b?gcd(b,a%b):a;
}

习题练习：

矩形切割

小明有一些矩形的材料，他要从这些矩形材料中切割出一些正方形。

当他面对一块矩形材料时，他总是从中间切割一刀，切出一块最大的正方形，

剩下一块矩形，然后再切割剩下的矩形材料，直到全部切为正方形为止。

例如，对于一块两边分别为 5 和 3 的材料（记为 5×3），小明会依次切出 3×3、2×2、1×1、1×1 共 4 个正方形。现在小明有一块矩形的材料，两边长分别是 2019 和 324。请问小明最终会切出多少个正方形？

题解部分：

考点：辗转求余、模拟

每次有选取剩下矩形的宽来作为正方形的边长

第一次切割：

2019 / 324 = 6 **** 75

第二次切割：

324 / 75 = 4 **** 24

第三次切割：

75 / 24 = 3 **** 3

第四次切割：

24 / 3 = 8

sum = 6 + 4 + 3 + 8 = 21；

递归实现：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e5+10;
int sum; 
LL gcd(LL a,LL b)
{
  return b?gcd(b,a%b),sum+=a/b:sum;
}
int main()
{
  gcd(2019,324);
  cout<<sum;
  return 0;
}

迭代模拟：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e5+10;
int sum; 
int main()
{
  int a=2019,b=324,r;
  while(b)
  {
  r=a%b;
  sum+=a/b;
  a=b;b=r;
  }
  cout<<sum;
  return 0;
}

最小公倍数

a与b的最小公倍数是两者的乘积与两者的最大公因数的商

最大公因数和最小公倍数的乘积等于原两个数的乘积。

实现代码：

int lcm(int a, int b)
{
  return a*b/gcd(a,b);
}

约数个数

任意一数字 N 都可以形成质因子相乘的形式： N = p 1 a ∗ p 2 b ∗ … ∗ p k x 任意一数字 N 都可以形成质因子相乘的形式：N=p1^a ∗p2^b∗…∗pk^x

任意一数字N都可以形成质因子相乘的形式：N=p1

∗p2

∗…∗pk

来复习一下

质因数分解

void divide(int x)
{
    for (int i = 2; i <= x / i; i ++ )//先枚举小于根号x的素数
        if (x % i == 0)
        {
            int s = 0;
            while (x % i == 0) x /= i, s ++ ;
            cout << i << ' ' << s << endl;
        }
    if (x > 1) cout << x << ' ' << 1 << endl;
    cout << endl;
}

给定 n 个正整数 a i ，请你输出这些数的乘积的约数个数，答案对 1 0 9 + 7 取模。给定 n 个正整数 a i，请你输出这些数的乘积的约数个数，答案对 10^9+7 取模。

给定n个正整数ai，请你输出这些数的乘积的约数个数，答案对10

+7取模。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL; 
const int mod = 1e9 + 7;
int main(){
    int n,x;
    LL ans = 1;
    unordered_map<int,int> hash;
    cin >> n;
    while(n--){
        cin >> x;
        for(int i = 2;i <= x/i; ++i){
            while(x % i == 0){
                x /= i;
                hash[i] ++;
            }
        }
        if(x > 1) hash[x] ++;
    }
    for(auto i : hash) ans = ans*(i.second + 1) % mod;
    cout << ans;
    return 0;

约数之和

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 110, mod = 1e9 + 7;
int main()
{
    int n;
    cin >> n;
    unordered_map<int, int> primes;
    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 p : primes)
    {
        LL a = p.first, b = p.second;
        LL t = 1;
        while (b -- ) t = (t * a + 1) % mod;
        res = res * t % mod;
    }
    cout << res << endl;
    return 0;
}

完结散花

ok以上就是对算法模版：数论之约数全家桶的全部讲解啦，很感谢你能看到这儿。如果有遗漏、错误或者有更加通俗易懂的讲解,欢迎小伙伴私信我，我后期再补充完善。

参考文献

https://www.acwing.com/activity/content/19/