蓝桥杯冲击-02约数篇(必考)

文章目录

前言

一、约数是什么

二、三大模板

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

 

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/1200.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

全面剖析OpenAI发布的GPT-4比其他GPT模型强在哪里

最强的文本生成模型GPT-4一、什么是GPT-4二、GPT-4的能力三、和其他GPT模型比较3.1、增加了图像模态的输入3.2、可操纵性更强3.3、复杂任务处理能力大幅提升3.4、幻觉、安全等局限性的改善3.6、风险和缓解措施改善更多安全特性3.7、可预测的扩展四、与之前 GPT 系列模型比较五、…

QT入门Item Views之QListView

目录 一、QListView界面相关 1、布局介绍 二、代码展示 1、创建模型&#xff0c;导入模型 2、 设置隔行背景色 3、删除选中行 三、源码下载 此文为作者原创&#xff0c;创作不易&#xff0c;转载请标明出处&#xff01; 一、QListView界面相关 1、布局介绍 先看下界面…

高完整性系统工程(三): Logic Intro Formal Specification

目录 1. Propositions 命题 2.1 Propositional Connectives 命题连接词 2.2 Variables 变量 2.3 Sets 2.3.1 Set Operations 2.4 Predicates 2.5 Quantification 量化 2.6 Relations 2.6.1 What Is A Relation? 2.6.2 Relations as Sets 2.6.3 Binary Relations as…

ZYNQ硬件调试-------day2

ZYNQ硬件调试-------day2 1.ILA&#xff08;Integrated Logic Analyzer &#xff09; 监控逻辑内部信号和端口信号;可以理解为输出。可单独使用 2.VIO&#xff08;Virtual Input/Output &#xff09; 实时监控和驱动逻辑内部信号和端口信号&#xff0c;可以理解为触发输入。不可…

第十四届蓝桥杯三月真题刷题训练——第 14 天

目录 第 1 题&#xff1a;组队 题目描述 运行限制 代码&#xff1a; 第 2 题&#xff1a;不同子串 题目描述 运行限制 代码&#xff1a; 思路&#xff1a; 第 3 题&#xff1a;等差数列 题目描述 输入描述 输出描述 输入输出样例 运行限制 代码&#xff1a; 思…

Dubbo原理简介

Dubbo缺省协议采用单一长连接和NIO异步通讯&#xff0c;适合于小数据量大并发的服务调用&#xff0c;以及服务消费者机器数远大于服务提供者机器数的情况。 作为RPC&#xff1a;支持各种传输协议&#xff0c;如dubbo,hession,json,fastjson&#xff0c;底层采用mina,netty长连接…

nginx详解(概念、Linux安装、配置、应用)

1.nginx是什么 百度百科 看百度百科的解释&#xff0c;第一句话就是错的。“Nginx (engine x) 是一个高性能的HTTP和反向代理web服务器”&#xff0c;从语法来看&#xff0c;去掉形容词就是&#xff1a;Nginx是服务器&#xff0c;nginx怎么会是服务器呢&#xff0c;nginx只是一…

Matlab进阶绘图第8期—聚类/分类散点图

聚类/分类散点图是一种特殊的特征渲染散点图。 聚类/分类散点图通过一定的聚类、分类方法&#xff0c;将特征相近的离散点划分到同一个类别中&#xff0c;进而将每个离散点赋予类别标签&#xff0c;并利用不同的颜色对不同的类别进行区分。 本文使用Matlab自带的gscatter函数…

C语言变量和数据类型的使用

文章目录前言一、将变量输出打印到控制台1.整形变量的输出2.浮点型变量的输出1.flaot的输出2.doble的输出3.float和double输出的区别4.%f,%10.2f......二、数据类型的大小总结前言 上一篇文章我们学习了C语言变量和数据类型的基本概念那么今天我们就具体的来看看如何在代码中使…

css实现文字大小自适应

在页面编写中经常会碰到页面自适应的问题&#xff0c;也就是页面内部的元素会随着窗口的放大缩小而放大缩小&#xff0c;box可以通过calc 百分比的形式做到页面自适应&#xff0c;但是box内的字体却无法做到这点&#xff0c;往往box自适应大小了&#xff0c;内部的字体还是原来…

selenium(5)-------自动化测试脚本(python)

1)alert框的处理 前提:我们是不可以通过控制台直接定位元素的方式去选中这个alert框的&#xff0c;例如说xpath直接进行定位元素 1)先获得弹框的操作句柄:alertdriver.switch_to.alert 2)再次调用accept方法进行关闭弹窗:alert.accept() from selenium import webdriver import…

强化学习分类与汇总介绍

1.强化学习&#xff08;Reinforcement Learning, RL&#xff09; 强化学习把学习看作试探评价过程&#xff0c;Agent选择一个动作用于环境&#xff0c;环境接受该动作后状态发生变化&#xff0c;同时产生一个强化信号(奖或惩)反馈给Agent&#xff0c;Agent根据强化信号和环境当…

【python刷题】leecode官方提示“->“,“:“这些符号是什么意思?什么是Type Hints?

作者&#xff1a;20岁爱吃必胜客&#xff08;坤制作人&#xff09;&#xff0c;近十年开发经验, 跨域学习者&#xff0c;目前于海外某世界知名高校就读计算机相关专业。荣誉&#xff1a;阿里云博客专家认证、腾讯开发者社区优质创作者&#xff0c;在CTF省赛校赛多次取得好成绩。…

JavaSE基础总结

JDK与JRE JDK&#xff0c;全称Java Development Kit&#xff0c;Java开发工具包 JRE&#xff0c;全称Java Runntime Environment&#xff0c;Java运行环境 JDK包含后者JRE。 JDK也可以说是Java SDK&#xff08;Software Development kit&#xff0c;软件开发工具包&#xff09;…

JVM高频面试题

1、项目中什么情况下会内存溢出&#xff0c;怎么解决&#xff1f; &#xff08;1&#xff09;误用固定大小线程池导致内存溢出 Excutors.newFixedThreadPool内最大线程数是21亿(2) 误用带缓冲线程池导致内存溢出最大线程数是21亿(3)一次查询太多的数据&#xff0c;导致内存占用…

基于深度学习的农作物叶片病害检测系统(UI界面+YOLOv5+训练数据集)

摘要&#xff1a;农作物叶片病害检测系统用于智能检测常见农作物叶片病害情况&#xff0c;自动化标注、记录和保存病害位置和类型&#xff0c;辅助作物病害防治以增加产值。本文详细介绍基于YOLOv5深度学习模型的农作物叶片病害检测系统&#xff0c;在介绍算法原理的同时&#…

百度的文心一言 ,没有想像中那么差

robin 的演示 我们用 robin 的演示例子来对比一下 文心一言和 ChatGPT 的真实表现&#xff08;毕竟发布会上是录的&#xff09;。 注意&#xff0c;我使用的 GPT 版本是 4.0 文学创作 1 三体的作者是哪里人&#xff1f; 文心一言&#xff1a; ChatGPT&#xff1a; 嗯&a…

C++ STL:vector的使用方法及模拟实现

目录 一. vector概述 二. vector接口函数的使用方法和模拟实现 2.1 vector类模板的成员变量 2.2 构造函数的使用和模拟实现 2.2.1 构造函数的使用方法 2.2.2 构造函数的模拟实现 2.3 析构函数的模拟实现 2.4 赋值运算符重载函数的使用和模拟实现 2.4.1 函数的使用 2.…

MybatisPlus------MyBatisX插件:快速生成代码以及快速生成CRUD(十二)

MybatisPlus------MyBatisX插件&#xff08;十二&#xff09; MyBatisX插件是IDEA插件&#xff0c;如果想要使用它&#xff0c;那么首先需要在IDEA中进行安装。 安装插件 搜索"MyBatisX"&#xff0c;点击Install&#xff0c;之后重启IDEA即可。 插件基本用途&…

蓝桥杯嵌入式第四课--定时器

前言蓝桥杯对于定时器这部分的考察主要集中在定时器中断、PWM输出以及输入捕获三个方面&#xff0c;本节课着眼于应用&#xff0c;介绍一下定时器的使用。定时器中断一、基础概念对没接触过定时器的新手来说&#xff0c;如果想要快速上手定时器的使用&#xff0c;首先要先对定时…