acgo题库
  • 首页
  • 题库
  • 学习
  • 天梯
  • 备赛

    竞赛

    • CSP-J/S
    • 蓝桥杯

    考级

    • GESP
    • CPA
    • 电子学会考级
  • 竞赛
  • 讨论
  • 团队
  • 商城
登录
注册
题目详情提交记录(0)
  • 题解

    不会真有人用这个模拟吧,这个240的数据量O(n)都够呛 那怎么办呢? 我们仔细读题,发现每个灯按开关的次数都是它们所有的因子数 所以我们要找到拥有奇数个因子数的数 但我们发现,如果一个数x有因子y,那它就必然有因子(x/y)等等我好像说过这句话,那怎么可能嘛! 我们再看一下样例, 好像有什么规律…… 我们用上面的代码把输入数调大点,如100 输出: ……等等,这些数都是完全平方数!!! 没错,完全任意平方数x因为有因子sqrt(x),而用x除以这个因子竟然还是sqrt(x)! 这样就减少了一个因子,因子数由偶数变成了奇数 所以我们只要输出n以内的完全平方数 时间复杂度:O(n)O(\sqrt{n})O(n )

    userId_undefined
    cjdst
    尊贵铂金CSP-S一等奖代码纠察员出题人
    106阅读
    2回复
    2点赞
  • 题解

    你要知道,想我这种想象力丰富的人都要先看看题解我看的题解 如果一个数它的因子数是奇数的话(首先必须保证它存在),那么它肯定是开着的 也就是说只要找到一个存在范围内的完全平方数并且输出即可

    userId_undefined
    元宝
    循环·循环打卡人I/O·IO入门者分支·分支解题者造物者
    2阅读
    0回复
    0点赞
暂无数据

提交答案之后,这里将显示提交结果~

首页