草庐IT

蓝桥杯每日一真题—— [蓝桥杯 2021 省 AB2] 完全平方数（数论，质因数分解）

孤独时代的c0re 2023-04-05 原文

文章目录

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

题目描述

一个整数 a a a 是一个完全平方数，是指它是某一个整数的平方，即存在一个 整数 b b b，使得 a = b 2 a=b^{2} a=b2 。

给定一个正整数 n n n，请找到最小的正整数 x x x，使得它们的乘积是一个完全平方数。

输入格式

输入一行包含一个正整数 n n n。

输出格式

输出找到的最小的正整数 x x x。

样例 #1

样例输入 #1

12

样例输出 #1

3

样例 #2

样例输入 #2

15

样例输出 #2

15

提示

对于 30 % 30 \% 30% 的评测用例, 1 ≤ n ≤ 1000 1 \leq n \leq 1000 1≤n≤1000，答案不超过 1000 1000 1000。

对于 60 % 60 \% 60% 的评测用例， 1 ≤ n ≤ 1 0 8 1 \leq n \leq 10^{8} 1≤n≤108，答案不超过 1 0 8 10^{8} 108。

对于所有评测用例， 1 ≤ n ≤ 1 0 12 1 \leq n \leq 10^{12} 1≤n≤1012，答案不超过 1 0 12 10^{12} 1012。

蓝桥杯 2021 第二轮省赛 A 组 G 题（B 组 H 题）。

思路：

这一看直接暴力就只能得一点点分，我还数论学的不太好先暴力得了30分。然后开始想办法吧！
没办法。。。看答案吧。。。

理论补充：完全平方数的一个性质：完全平方数的质因子的指数一定为偶数

1.唯一分解定理任意一个数 n，它都可以分解为若干个质数的乘积。

2.需要知道完全平方数的一个性质：完全平方数的质因子的指数一定为偶数。附上大佬的证明过
程：

最终思路：

对n进行质因数分解，如果质因数的指数为奇数的话就在x中乘以这个质因子这样，可以让指数保持偶数，如果是偶数那就不用管它~~~~
1.分解质因子：

for (long long i = 2; i * i <= n; i++)
    {
        if (n % i == 0)
        {
            cnt++;//记录有多少个因子，后面好遍历
        }

        while (n % i == 0)
        {
            a[cnt] = i;//a数组存因子
            g[cnt]++;//g数组存因子指数
            n = n / i;
        }
    }

    if (n > 1)
    {
        a[++cnt] = n;
        g[cnt]++;
    }//考虑没分解完的情况

2,根据性质得出答案：

  for (int i = 1; i <= cnt; i++)//遍历如果有奇数就让原来的n*ans*这个奇数质因子也就是让ans*这个奇数质因子
    {
        if (g[i] % 2)
        {
            ans = ans * a[i];
        }
    }
    cout << ans;

小插曲：

质因数分解写错了最后输出了和n一样的数竟然得了60分！！

全部代码

#include <iostream>
using namespace std;

long long n, ans = 1, g[1000], a[1000], cnt;
int main()
{
    cin >> n;
    // 首先对n进行质因数分解
    for (long long i = 2; i * i <= n; i++)
    {
        if (n % i == 0)
        {
            cnt++;//记录有多少个因子，后面好遍历
        }

        while (n % i == 0)
        {
            a[cnt] = i;//a数组存因子
            g[cnt]++;//g数组存因子指数
            n = n / i;
        }
    }

    if (n > 1)
    {
        a[++cnt] = n;
        g[cnt]++;
    }//考虑没分解完的情况
    //完全平方数的质因子的指数一定为偶数
    for (int i = 1; i <= cnt; i++)//遍历如果有奇数就让原来的n*ans*这个奇数质因子也就是让ans*这个奇数质因子
    {
        if (g[i] % 2)
        {
            ans = ans * a[i];
        }
    }
    cout << ans;
    system("pause");
    return 0;
}
蓝桥质因数spanclasstoken蓝桥杯$算法

有关蓝桥杯每日一真题—— [蓝桥杯 2021 省 AB2] 完全平方数（数论，质因数分解）的更多相关文章

  1. ruby - 完全离线安装RVM - 2

    我打算为ruby​​脚本创建一个安装程序，但我希望能够确保机器安装了RVM。有没有一种方法可以完全离线安装RVM并且不引人注目(通过不引人注目，就像创建一个可以做所有事情的脚本而不是要求用户向他们的bash_profile或bashrc添加一些东西)我不是要脚本本身，只是一个关于如何走这条路的快速指针(如果可能的话)。我们还研究了这个很有帮助的问题:RVM-isthereawayforsimpleofflineinstall?但有点误导，因为答案只向我们展示了如何离线在RVM中安装ruby。我们需要能够离线安装RVM本身，并查看脚本https://raw.github.com/wayn

  2. ruby-on-rails - Ruby on Rails 3 中的类方法——我完全迷路了! - 2

    背景here.在上面的链接中，给出了以下示例:classauthor.id)endend除了这种语法对于像我这样的初学者来说很陌生——我一直认为类方法是用defself.my_class_method定义的——我在哪里可以找到关于类的文档RubyonRails中的方法？据我所知，类方法总是在类本身(MyClass.my_class_method)上调用，但如果R​​ails中的类方法是可链接的，似乎必须进行其他操作在这里!编辑:我想我通过对类方法的语法发表评论有点被骗了。我真的想问Rails如何使类方法可链接—我了解方法链接的工作原理，但不知道Rails如何允许您链接类方法而无需实际返

  3. ruby - 如何使用私钥加密完全加密 Ruby 中的数据？ - 2

    首先，关于我们系统的一些信息，它基本上是建筑行业的电子招标解决方案。所以:列表项我们的系统有多家公司每个公司都有多个用户每家公司可以创建多个拍卖然后其他公司可以为可用的拍卖提交他们的出价。一个出价包含数百或数千个单独的项目，我们只需要加密这些记录的“价格”部分。我们面临的问题是，我们的大客户不希望我们知道投标价格，至少在投标过程中是这样，这是完全可以理解的。现在，我们只是通过对称加密对价格进行加密，因此即使价格在数据库中有效加密，他们担心的是我们拥有解密价格的key。因此，我们正在研究某种形式的公钥加密系统。以下是我们对解决方案的初步想法:当一家公司注册时，我们会使用OpenSSL为其

  4. ruby-on-rails - ruby 真的是一种完全面向对象的语言吗？ - 2

    Ruby是完全面向对象的语言。在ruby​​中，一切都是对象，因此属于某个类。例如5属于Objectclass1.9.3p194:001>5.class=>Fixnum1.9.3p194:002>5.class.superclass=>Integer1.9.3p194:003>5.class.superclass.superclass=>Numeric1.9.3p194:005>5.class.superclass.superclass.superclass=>Object1.9.3p194:006>5.class.superclass.superclass.superclass.su

  5. 华为OD机试真题 C++ 实现【带传送阵的矩阵游离】【2023 Q2 | 200分】 - 2

            所有题目均有五种语言实现。C实现目录、C++实现目录、Python实现目录、Java实现目录、JavaScript实现目录题目n行m列的矩阵，每个位置上有一个元素你可以上下左右行走，代价是前后两个位置元素值差的绝对值.另外，你最多可以使用一次传送阵(只能从一个数跳到另外一个相同的数)求从走上角走到右下角最少需要多少时间。输入描述：第一行两个整数n,m，分别代表矩阵的行和列。后面n行，每行m个整数，分别代表矩阵中的元素。输出描述：一个整数，表示最少需要多少时间。

  6. 蓝桥杯备赛（二） - 2

    目录前言： 一、ASC分析代码实现二、 卡片分析代码实现三、 直线分析代码实现四、货物摆放分析代码实现小结：前言：  在刷题的过程中，发现蓝桥杯的题目和力扣的差别很大。让人有一种不一样的感觉，蓝桥杯题目偏向对于实际问题用编程去的解决，而力扣给人感觉很锻炼自己的编程思维，逻辑能力。两者结合去刷，相信会有不一样的收获。 一、ASC  已知大写字母A的ASCII码为65，请问大写字母L的ASCII码是多少？分析  这道题目看上去很简单，我们需确定自己计算的准确，所以我建议用编程去解决。代码实现publicclassTest8{publicstaticvoidmain(String[]args){Sy

  7. ruby-on-rails - 给定长度的完全随机标识符 - 2

    我想生成一个包含数字、字母和特殊字符的给定(长度可能不同)长度的完全随机的“唯一”(我将确保使用我的模型)标识符例如:161551960578281|2.AQAIPhEcKsDLOVJZ.3600.1310065200.0-514191032|有人可以建议在RubyonRails中最有效的方法吗？编辑:重要:如果可能，请评论您提出的解决方案的效率，因为每次用户进入网站时都会使用它!谢谢 最佳答案 将其用于访问token与UUID不同。您不仅需要伪随机性，而且还需要加密安全PRNG.如果您真的不关心您使用的是什么字符(它们不会增加任何

  8. ruby-on-rails - 如何完全重新加载 ActiveRecord 以重置其内存值？ - 2

    在RSpec测试中，我创建了一个记录，其中包含多个内存值。foo.reload对对象的属性按预期工作，但内存的属性仍然存在。到目前为止，它通过完全重新创建对象来工作:foo=Foo.find(123)但在我的例子中，查找记录的逻辑实际上更复杂。什么是完全重新加载记录并删除所有内存值的好方法？ 最佳答案 好的方法是您已有的方法:完全重新创建对象。您不能以任何简单的“Rails”方式“重新加载”对象的内存值，因为内存属性不是Rails或ActiveRecord的功能。两者都不知道您是如何内存方法的。

  9. ruby - 类完全加载后运行代码 - 2

    classAdo_something_from_bdefmethod_in_aendendmoduleBdefself.includedbasebase.extendClassMethodsendmoduleClassMethodsdefdo_something_from_bA.class_evaldoalias_method:aliased_method_in_a,:method_in_aendendendendA.send(:include,B)该代码将失败，因为当调用do_somethind_from_b时，method_in_a尚不存在。那么有没有一种方法可以在classA完全

  10. ruby - 如何强制 Float 在不使用科学记数法的情况下以完全精确的方式显示，而不是作为字符串显示？ - 2

    在Ruby中，如何在没有科学记数法的情况下强制显示所有重要位置/完全精确的float？目前我将BigDecimal转换为Float，BigDecimal(0.000000001453).to_f，但这会产生1.453e-09的结果float。如果我执行类似"%14.12f"%BigDecimal("0.000000001453").to_f的操作，我会得到一个字符串。然而，在这种情况下，字符串作为输出是NotAcceptable，因为我需要它作为没有科学记数法的实际数字float。---编辑---好吧，让我在这里提供一些背景信息，这可能需要更改我原来的问题。我正在尝试使用Highsto

随机推荐