acgo题库
  • 首页
  • 题库
  • 题单
  • 竞赛
  • 讨论
  • 排行
  • 团队
  • 备赛专区

    竞赛

    • CSP-J/S
    • 蓝桥杯

    考级

    • GESP
    • CPA
    • 电子学会考级
登录
注册
题目详情题解(0)讨论(0)提交记录(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

    复仇者_帅童

    小有名气CSP-J一等奖出题人
    67阅读
    2回复
    1点赞
  • 2个题解

    1: 2:

    userId_undefined

    john

    34阅读
    0回复
    1点赞
  • 题解

    userId_undefined

    zsy

    7月全勤卷王题解仙人出道萌新时间刺客时空双修者秩序白银
    1阅读
    0回复
    0点赞
  • 题解

    userId_undefined

    无敌的鳖佬仔给老爷爷猜猜被

    7月全勤卷王时间刺客空间掌握者循环·循环打卡人荣耀黄金I/O·IO入门者
    0阅读
    0回复
    0点赞
首页