首页 > 其他分享 >约数总结

约数总结

时间:2023-08-17 23:03:03浏览次数:38  
标签:约数 总结 ... int alpha include divisors

试除法求约数

方法1-试除所有数

算法原理

假设p是x的一个约数,那么x/p一定也是它的约数,所以只需枚举2 到 $\sqrt[2]{n}$的约数,并且可以直接通过运算获得 $\sqrt[2]{n}$ 之后对应的那个约数 时间复杂度$O(\sqrt{n})$

代码实现

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

vector<int> get_divisors(int x)
{
    vector<int> res;
    for (int i = 1; i <= x / i; ++ i)
        if (x % i == 0)
        {
            res.push_back(i);
            if (i != x / i) res.push_back(x / i);
        }
    sort(res.begin(), res.end());
    return res;
}
int main()
{
    int n;
    cin >> n;
    while (n --)
    {
        int x;
        cin >> x;
        auto res = get_divisors(x);
        for (int t : res) cout << t << ' ';
        cout << endl;
    }
    return 0;
}

方法2:质因数分解 + dfs

算法原理 此做法的原理和计算所有约数的和有些类似,属于排列组合问题。 对于每个质数,我们选择其一种指数情况,所有质数相乘在一些就属于一个约数,暴搜所有情况即可(暴搜具有可行性的原因是int范围内具有约数最多的数具有1600个约数,情况很少,暴搜是可以实现的)

算法流程

  1. 首先使用线性筛获取所需范围的质数
  2. 对数据进行质因数分解
  3. dfs获取所有约数

代码实现

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

typedef pair<int, int> PII;

const int N = 50010;

int primes[N], cnt;
bool st[N];
PII primes_factor[N];
int divisors[N];
int cntf, cntd;

void init(int n)
{
    for (int i = 2; i <= n; ++ i)
    {
        if (!st[i]) primes[cnt ++] = i;
        for (int j = 0; primes[j] * i <= n; ++ j)
        {
            st[primes[j] * i] = true;
            if (i % primes[j] == 0) break;
        }
    }
}
void dfs(int u, int p)
{
    if (u == cntf)
    {
        divisors[cntd ++] = p;
        return ;
    }
    for (int i = 0; i <= primes_factor[u].second; ++ i)
    {
        dfs(u + 1, p);
        p *= primes_factor[u].first;
    }
}
void get_divisors(int n)
{
    cntf = 0;
    for (int i = 0; i < cnt; ++ i)
    {
        int p = primes[i];
        if (n % p == 0)
        {
            int s = 0;
            while (n % p == 0)
            {
                ++ s;
                n /= p;
            }
            primes_factor[cntf ++] = {p, s};
        }
    }
    if (n > 1) primes_factor[cntf ++] = {n, 1};
    
    cntd = 0;
    dfs(0, 1);
}
int main()
{
    init(50000);
    
    int n;
    cin >> n;
    
    while (n --)
    {
        int x;
        cin >> x;
        
        get_divisors(x);
        
        sort(divisors, divisors + cntd);
        for (int i = 0; i < cntd; ++ i) cout << divisors[i] << ' ';
        cout << endl;
    }
    return 0;
}

计算约数个数

int范围内具有最多约数的数拥有$1600$个约数

算法原理

根据唯一分解定理,任意数n可表示为 $ n = p_1^{\alpha_1} * p_2^{\alpha_2} * ... * p_n^{\alpha_n} $, 选择一定量的 $ P_1 , P_2, ... ,P_n $ 相乘获得n的约数,总的选择方案为$(\alpha_1 + 1) * (\alpha_2 + 1) * ... * (\alpha_n + 1)$,其中加1表示指数可以为0

代码实现

#include <iostream>
#include <algorithm>
#include <unordered_map>

using namespace std;

const int MOD = 1e9 + 7;

unordered_map<int, int> primes;

inline void get_divisors(int x)
{
    for (int i = 2; i <= x / i; ++ i)
        while (x % i == 0)
        {
            x /= i;
            ++ primes[i];
        }
    if (x > 1) ++ primes[x];
}
int main()
{
    int x;
    cin >> x;
    get_divisors(x);
    
    long long res = 1;
    for (auto prime : primes) res = res * (prime.second + 1) % MOD;
    cout << res << endl;
    return 0;
}

计算所有约数的和

算法思想

$(p_1^{\alpha_1} + p_1^{\alpha_2} + ... + p_2^{\alpha_n}) * (p_2^{\alpha_1} + p_2^{\alpha_2} + ... + p_2^{\alpha_n}) * ... * (p_n^{\alpha_1} + p_n^{\alpha_2} + ... + p_n^{\alpha_n})$,展开之后一共是$(\alpha_1 + 1) * (\alpha_2 + 1) * ... * (\alpha_n + 1)$项,每一项的形式均为$ p_1^{k_1} * p_2^{k_2} * ... * p_n^{k_n} $,即每一项都是一个约数,所有约数加在一起即为答案

代码实现

代码中计算 $ p_1^{0} + p_1^{1} + ... + p_2^{\alpha_1}$ 时候采用了非常巧妙的做法。可以概括为当我们计算 $\sum_{i = 0}^{\alpha}p^i$ 这种求和时,可以采用下面的代码

int t = 1; // 最终结果
while(a --) // a表示p的最大指数
    t = t * p + 1;
#include <iostream>
#include <unordered_map>

using namespace std;

int n;
const int MOD = 1e9 + 7;

unordered_map<int, int> primes;

void get_divisors(int x)
{
    for (int i = 2; i <= x / i; ++ i)
        while (x % i == 0)
        {
            x /= i;
            ++ primes[i];
        }
    if (x > 1) ++ primes[x];
}
int main()
{
    int x;
    cin >> x;
    get_divisors(x);
    
    long long res = 1;
    for (auto prime : primes)
    {
        int p = prime.first, a = prime.second;
        long long t = 1;
        while (a --) t = (t * p + 1) % MOD;
        res = res * t % MOD;
    }
    cout << res << endl;
    return 0;
}

计算倍数个数

1到n中p的倍数(或者说能被p整除)的数有 $\lfloor \frac{n}{p} \rfloor$ 个

原理很简单,1到n中p的倍数为 $1p, 2p, 3p, ... kp$,当$kp$恰好等于n时,总个数为 $\frac {n}{p}$;当$kp<n$ 且 $(k+1)*p>n$ 时,总个数为 $\lfloor \frac{n}{p} \rfloor$。将两种情况结合在一起就是$\lfloor \frac{n}{p} \rfloor$

1到n中既是$p_1$的倍数,又是$p_2$的倍数有 $\lfloor \frac{n}{p_1 \ * \ p_2} \rfloor$ 个($p_1$ 和 $p_2$保证互质)

首先我们假设$p_1$和$p_2$是两个不相等的质数且m既是$p_1$的倍数(为了后续公式的简便,这里假设就是1倍的关系),又是$p_2$的倍数(同前),根据唯一分解定理,m的质因数分解式中一定是$p_1 \ * \ p_2 \ * \ ...$的形式,所以m一定可以整除 $p_1 \ * \ p_2$,所以也就是求1到n中$p_1 \ * \ p_2$倍数的个数。 上述公式中,对于$p_1$ 和 $p_2$的要求是保证互质即可,并没有限制必须均为质数,原因在于即使两个数中存在合数,比如4和7,但是由于两个数是互质的,所以两者质因数分解的结果中一定不包含相同的质因子,所以和上面两个数均是质数的情况一样,如果某数m是4和7的倍数,那么它一定是4*7的倍数。 综上所述,上述公式是正确的。

标签:约数,总结,...,int,alpha,include,divisors
From: https://blog.51cto.com/u_14882565/7128294

相关文章

  • 约数总结
    试除法求约数方法1-试除所有数算法原理假设p是x的一个约数,那么x/p一定也是它的约数,所以只需枚举2到$\sqrt[2]{n}$的约数,并且可以直接通过运算获得$\sqrt[2]{n}$之后对应的那个约数时间复杂度$O(\sqrt{n})$代码实现#include<iostream>#include<algorithm>#include<......
  • 第五周总结
    这周把mapreduce的课程学习完毕了主要练习了mapreduce里面基本的wordcount操作,切片分区操作,排序方法,outputformat的运行流程,etl数据过滤的方法,文件压缩在mapreduce里面的执行方法。最后还看了yarn的基本概念和操作流程。......
  • 20230816巴蜀暑期集训测试总结
    T1这题一看就很难实现,事实也确实是这样,考场想了半个多小时没有思路,打完暴力就跳了。这道题的正解技巧和思维性很强,不是很套路,只是融合了一些线段树区间操作的思想。感觉......怎么会评蓝呢?这T4一道紫题都明显比T1好做啊!关键T1的考场通过率竟然最高!大概思路就是,变化会形......
  • 2016考研英语:考研作文重要词组总结
    2016考研英语:考研作文重要词组总结 2015-06-11 北京世纪高教编辑部  英语考研写作如果记住一些常用谚语和词组,一定能快速提高作文分数,下面总结的这些谚语及词组希望能助到大家取得好成绩。 一.写作常用谚语1.A friend in need is a friend indeed. ......
  • 8.14总结
    总结题外话:方舟题打得这么烂活该保底t1比赛时阿能和德狗看反,暴毙100(样例太水&赌一把t2想到线段树优化建边+拓扑但是一根筋没有建虚点,也没有将每一个区间去除特殊点变成几个小区间所以在拓扑时的入度就寄飞了t3正经50就差一个线段树优化查询t4毒瘤题目详情请见神秘代码......
  • Spring源码学习笔记13——总结篇, 从IOC到AOP
    系列文章目录和关于我零丶序言在《Spring源码学习笔记12——总结篇,IOC,Bean的生命周期,三大扩展点》中,我们总结了SpringIOC部分的知识,为了更好的给群里的伙伴们分享SpringAOP的知识,遂有了这篇文章,这篇文章将从IOC聊到AOP,其中IOC不会那么细致,重点还是在AOP。一丶引入1.AOP概述......
  • 21硬件总结
    应组长要求,为以后硬件留下知识,避免硬件出现几乎从零开始的局面,本人水平而且文笔有限,只能告诉一些经验之谈,知识相对来说我只是菜狗,希望一届比一届进步吧。首先,就规范来说,对于实验室,是非常必要的,你的原理图,PCB不仅仅你一个人看,你要给你的队友,其他硬件,师弟或者“师妹”看,画......
  • 【考后总结】CSP-S 模拟 6
    8.17CSP模拟23That'sWhyYouGoAway-MichaelLearnsToRockBabywon'tyoutellmewhythereissadnessinyoureyesIdon'twannasaygoodbyetoyouLoveisonebigillusionIshouldtrytoforgetButthereissomethingleftinmyhea......
  • sqli-labs-BasicLevel-总结
    title:sqli-labsbasicchallengesdate:2023-08-0416:34:03categories:CTF-Web入门description:1~20总结常用的MySql命令总结查库:selectschema_namefrominformation_schema.schemata查表:selecttable_namefrominformation_schema.tableswheretable_schema='s......
  • 【狂神说Java】Java零基础学习笔记-JavaSE总结
    【狂神说Java】Java零基础学习笔记-JavaSE总结JavaSE总结:......