[蓝桥杯 2021 省 AB2] 完全平方数

news/2024/5/26 19:37:54/文章来源:https://blog.csdn.net/hydrogend/article/details/136591710

一、题目描述

P8754 [蓝桥杯 2021 省 AB2] 完全平方数

二、问题简析

2.1 唯一分解定理

唯一分解定理:大于1的自然数都可以唯一地写成素数的积

由该定理,一个大于 1 1 1 的自然数 b b b 可以表示为 b = a 1 p 1 ∗ a 2 p 2 ∗ . . . ∗ a n p n b=a_1^{p_1}*a_2^{p_2}*...*a_n^{p_n} b=a1p1a2p2...anpn ( a 1 , a 2 , . . . , a n a_1, a_2, ..., a_n a1,a2,...,an素数 p 1 , p 2 , . . . , p n p_1, p_2, ..., p_n p1,p2,...,pn 为对应的指数,即有 p n p_n pn 个该数)。该自然数 b b b 的平方为 b 2 = a 1 2 p 1 ∗ a 2 2 p 2 ∗ . . . ∗ a n 2 p n b^2 = a_1^{2p_1}*a_2^{2p_2}*...*a_n^{2p_n} b2=a12p1a22p2...an2pn,所有的指数都是偶数
我们可以得到,若一个自然数是完全平方数,则将该自然数写出素数的积后,每个素数的指数一定是偶数。

因此,我们可以分解 n n n,将指数不为偶数的素数相乘,就得到了 x x x

2.2 分解自然数

以下代码给出了如何将大于 1 1 1 的自然数分解为素数的积。

// 将整数n分解成若干个素数,除1和本身
map<int, int> factors(int n)
{map<int, int> ans;      // 分解n后,有ans[i]个i// n==1,特殊考虑if (n == 1){ans[n] = 1;return ans;}// 1和本身总是因数,这里忽略for (int i = 2; i * i <= n; i++){// 可能有若干个iwhile (n % i == 0){ans[i]++;       // 分解出一个in /= i;}}if (n != 1)             // n==1,已经分解完了ans[n] += 1;return ans;
}

三、AC代码

#include <bits/stdc++.h>using namespace std;
typedef long long ll;int quickin(void)
{int ret = 0;bool flag = false;char ch = getchar();while (ch < '0' || ch > '9'){if (ch == '-')    flag = true;ch = getchar();}while (ch >= '0' && ch <= '9' && ch != EOF){ret = ret * 10 + ch - '0';ch = getchar();}if (flag)    ret = -ret;return ret;
}int main()
{#ifdef LOCALfreopen("test.in", "r", stdin);#endifll n, ans = 1;cin >> n;if (n == 1){cout << 4 << endl;return 0;	}for (ll i = 2; i * i <= n; i++){ll cnt = 0;while (n % i == 0){cnt += 1;n /= i;	}if (cnt % 2 != 0)    ans *= i;}if (n != 1)    ans *= n;cout << ans << endl;return 0;
}

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

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

相关文章

OPPO后端二面,凉了!

这篇文章的问题来源于一个读者之前分享的 OPPO 后端凉经&#xff0c;我对比较典型的一些问题进行了分类并给出了详细的参考答案。希望能对正在参加面试的朋友们能够有点帮助&#xff01; Java String 为什么是不可变的? public final class String implements java.io.Seri…

从GPT入门,到R语言基础与作图、回归模型分析、混合效应模型、多元统计分析及结构方程模型、Meta分析、随机森林模型及贝叶斯回归分析综合应用等专题及实战案例

目录 专题一 GPT及大语言模型简介及使用入门 专题二 GPT与R语言基础与作图&#xff08;ggplot2&#xff09; 专题三 GPT与R语言回归模型&#xff08;lm&glm&#xff09; 专题四 GPT与混合效应模型&#xff08;lmm&glmm&#xff09; 专题五 GPT与多元统计分析&…

Linux--vim

一.什么是vim Vim&#xff08;Vi IMproved&#xff09;是一种文本编辑器&#xff0c;通常在Linux和其他类Unix操作系统中使用。它是Vi编辑器的增强版本&#xff0c;提供了更多的功能和定制选项。Vim具有强大的文本编辑和编程功能&#xff0c;支持语法高亮、代码折叠、宏录制、…

Nodejs 第五十五章(socket.io)

传统的 HTTP 是一种单向请求-响应协议&#xff0c;客户端发送请求后&#xff0c;服务器才会响应并返回相应的数据。在传统的 HTTP 中&#xff0c;客户端需要主动发送请求才能获取服务器上的资源&#xff0c;而且每次请求都需要重新建立连接&#xff0c;这种方式在实时通信和持续…

yolov8模型结构

yolov8模型结构 yolo发展历史yolov8简介yolov8模型结构 yolo发展历史 YOLOv1&#xff1a;2015年Joseph Redmon和 Ali Farhadi等 人&#xff08;华盛顿大学&#xff09; YOLOv2&#xff1a;2016年Joseph Redmon和Ali Farhadi等人&#xff08;华盛顿大学&#xff09; YOLOv3&…

鸿蒙Harmony应用开发—ArkTS声明式开发(基础手势:TextClock)

TextClock组件通过文本将当前系统时间显示在设备上。支持不同时区的时间显示&#xff0c;最高精度到秒级。 说明&#xff1a; 该组件从API Version 8开始支持。后续版本如有新增内容&#xff0c;则采用上角标单独标记该内容的起始版本。 子组件 无 接口 TextClock(options?…

使用API有效率地管理Dynadot域名,使用API设置域名隐私保护

关于Dynadot Dynadot是通过ICANN认证的域名注册商&#xff0c;自2002年成立以来&#xff0c;服务于全球108个国家和地区的客户&#xff0c;为数以万计的客户提供简洁&#xff0c;优惠&#xff0c;安全的域名注册以及管理服务。 Dynadot平台操作教程索引&#xff08;包括域名邮…

java代码将mysql表数据导入HBase表

java代码将mysql表数据导入HBase表 目录 一、项目目录介绍 二、主要接口方法与调用 三、全局配置文件 四、执行方式和输出介绍 五、项目依赖 一、项目目录介绍 主要包含四个接口:Com、RDB、HBase、RDBToHBase和其实现类xxxImpl。 两个配置文件:log4j日志配置文件log4j.pro…

Android App冷启动耗时优化

Android应用启动过程 Android应用启动过程&#xff0c;主要包含app::onCreate及执行前的Application阶段及Activity::onCreate执行之后的Activity阶段&#xff0c;以及两个阶段之间的间隙handleMessage阶段和最终页面渲染上屏完成前数据加载阶段四个区间组成。 具体来看&#x…

在 Android 上恢复已删除文件的 5 种简单方法

您可能会因为意外删除、未完成的 Android 更新、手机意外关机等原因而丢失 Android 上的重要数据。新技术的发展使许多手机功能或程序能够从内部恢复丢失的数据。 在 Android 上恢复已删除文件的 5 种简单方法 然而恢复成功率的不确定性也成为人们克服数据丢失困境的重要考虑因…

SQL语句在MySQL中的执行过程

有一条SQL语句&#xff0c;给到MySQL,是怎么被执行的 基本架构 连接器&#xff1a;进行身份认证&#xff0c;确定操作权限 查询缓存&#xff1a; 执行查询语句时&#xff0c;先查询缓存&#xff08;不太实用&#xff0c;MySQL 8.0 版本后删了&#xff09; 分析器&#xff1a…

运放的基础知识

运算放大器&#xff08;Operational Amplifier&#xff0c;简称运放&#xff09;是一种直流耦合、差模&#xff08;差动模式&#xff09;输入的高增益电压放大器&#xff0c;通常具有单端输出。它能产生一个相对于输入端电势差大数十万倍的输出电势&#xff08;对地而言&#x…

鸿蒙培训开发:就业市场的新热点~

金三银四在即&#xff0c;随着春节假期结束&#xff0c;各行各业纷纷复工复产&#xff0c;2024年的春季招聘市场也迎来了火爆的局面。最近发布的《2024年春招市场行情周报&#xff08;第一期&#xff09;》显示&#xff0c;尽管整体就业市场仍处于人才饱和状态&#xff0c;但华…

2024年华为HCIA-DATACOM新增题库(H12-811)

801、[单选题]178/832、在系统视图下键入什么命令可以切换到用户视图? A quit B souter C system-view D user-view 试题答案&#xff1a;A 试题解析&#xff1a;在系统视图下键入quit命令退出到用户视图。因此答案选A。 802、[单选题]“网络管理员在三层交换机上创建了V…

西井科技参与IATA全球货运大会 以AI绿动能引领智慧空港新未来

3月12日至14日&#xff0c;由国际航空运输协会IATA主办的全球货运大会&#xff08;World Cargo Symposium&#xff09;在中国香港成功举办&#xff0c;这是全球航空货运领域最大规模与影响力的年度盛会。作为大物流领域全球领先的“智能化与新能源化”综合解决方案提供商&#…

【数学建模】Topsis法python代码

昨天学习了Topsis法的基本概念&#xff0c;今天就来一起实践一下&#xff0c;用python实现topsis法 代码分块解释 1、引入numpy库 numpy as np 2、输入参评与指标数目 # 用户输入参评数目和指标数目&#xff0c;将输入的字符串转换为数值 print("请输入参评数目&#…

DHCP中继实验(思科)

华为设备参考&#xff1a;DHCP中继实验&#xff08;华为&#xff09; 一&#xff0c;技术简介 DHCP中继&#xff0c;可以实现在不同子网和物理网段之间处理和转发DHCP信息的功能。如果DHCP客户机与DHCP服务器在同一个物理网段&#xff0c;则客户机可以正确地获得动态分配的IP…

QT开发(二) 构建QMainWindow

1、前言 QMainWindow是Qt框架中用于创建应用程序主窗口的类。它是许多GUI应用程序的基础&#xff0c;提供了丰富的功能和灵活性&#xff0c;以支持用户界面的创建和管理。 QMainWindow的结构主要包括以下几个部分&#xff1a; 菜单栏&#xff08;Menu Bar&#xff09;&#…

C++:vector类

vector的介绍及使用 1. vector 是表示可变大小数组的序列容器。 2. 就像数组一样&#xff0c; vector 也采用的连续存储空间来存储元素。也就是意味着可以采用下标对 vector 的元素进行访问&#xff0c;和数组一样高效。但是又不像数组&#xff0c;它的大小是可以动态改变的…

金山办公内推

作为金山办公刚刚校招等待入职的一员&#xff0c;我诚挚地邀请您加入我的内推计划&#xff0c;与我一起共同打造卓越的工作环境和未来。 我能帮你 &#xff08;与直接填我的内推码不同&#xff0c;我直接通过内部问卷帮你投&#xff09; 1&#xff0c;直接通过校招群里的连接…