快速计算约数的个数——从基础到高级

举报
攻城狮杰森 发表于 2022/06/29 21:41:15 2022/06/29
【摘要】 题目来源:【欧拉计划第 12 题】 高度可除的三角数 Highly divisible triangular number这道题我们在枚举完三角数后,最重要的是去判断何时某个三角数约数的个数大于 500下面我们来看下,针对计算约数的个数问题,用不同的算法解决,逐步求得最优解 方法 1最简单,更是非常容易理解的方法复杂度:O(n2)\large O_{\left ( n^{2} \right ...

题目来源:【欧拉计划第 12 题】 高度可除的三角数 Highly divisible triangular number

这道题我们在枚举完三角数后,最重要的是去判断何时某个三角数约数的个数大于 500

下面我们来看下,针对计算约数的个数问题,用不同的算法解决,逐步求得最优解

方法 1

最简单,更是非常容易理解的方法

复杂度: O ( n 2 ) \large O_{\left ( n^{2} \right )}

主要思想:定义变量,使其在小于传入判断值的条件下从 1 开始自增,如果判断值和该变量进行模取运算后的值为 0,则说明该变量此时的值是判断值得一个约数。那么,程序计数器自增,记录下此值。循环结束后,输出计数器保存的值即为判断值约数的个数

这种方法优点除易于理解外,怕是没有优点了。缺点当然就是时间复杂度太高,一个值就需要去从 1 一直判断到该值。试想,如果数据量呈指数增长,这种方法恐怕在一般的计算机上不容易很快得到答案

实现代码如下

int check(long long n)
{
    int count = 0;
    long long i = 1; //注意数据范围
    while (i <= n)
    {
        if (n % i == 0) //成立,这说明此时 i 为 n 的一个约数
        {
            count++; //计数器自增
        }
        i++; //继续判断下一个数字是否为 i 的约数
    }
    return count;
}

方法 2

复杂度: O ( n ) \large O_{\left ( \sqrt{n} \right )}

主要思想:对比可以看出,方法一和方法二差别不大,但影响最关键的是它们的复杂度,直接由 O ( n 2 ) O_{\left ( n^{2} \right )} 降至 O ( n ) O_{\left ( \sqrt{n} \right )}

同样,仍然是暴力枚举,只不过这里的判断条件由 i < = n 变为 i * i < = n,复杂度优化了些许。进入 for() 循环后,如果 n % i == 0 ,那么说明此时的 i 值是 n 的一个约数

大家在这里要注意的是 if...else 语句内容,这里主要解释下此处和方法一的差别

举个例子,如果 n = 4i = 2,满足 2 × 2 = 4 的条件,但此时 4 的两个约数 2 相当于一个,程序计数器只能自增 1 ,而不是 2

当然,如果进入 for() 循环后,不满足条件 i * i = n ,那么自然是两个不同的约数,此时程序计数器需要增加 2,而不是 1

int check(long long n)
{
    int count = 0;
    for (long long i = 1; i * i <= n; i++)
    {
        if (n % i == 0)
        {
            if (i * i == n) // 区别所在,重点理解
                count++;
            else
                count += 2;
        }
    }
    return count;
}

方法 3

试除法求解

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;
}

LeetCode 题解思路

方法四

约数个数定理

设一个数可以表示为其素数幂的乘积,即:

n = p 1 e 1 p 2 e 2 p m e m \large n={p_{1}}^{e_{1}} \cdot {p_{2}}^{e_{2}} \cdot\cdot\cdot {p_{m}}^{e_{m}}

则该数的约数个数为:

( e 1 + 1 ) ( e 2 + 1 ) ( e m + 1 ) \large \left ( e_{1}+1 \right )\cdot \left ( e_{2}+1 \right )\cdot \cdot \cdot \left ( e_{m}+1 \right )

参考代码:

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int N, n, i, s, r;
    while (scanf("%d", &N) != EOF)
    {
        while (N--)
        {
            cin >> n;
            s = 1;
            for (i = 2; i * i <= n; i++)
            {
                r = 0;
                while (n % i == 0)
                {
                    r++;
                    n /= i;
                }
                if (r > 0)
                {
                    r++;
                    s *= r;
                }
            }
            if (n > 1)
                s *= 2;
            cout << s;
        }
    }
    return 0;
}
【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息, 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。