哈哈哈哈哈哈哈嗝QwQ 2022-05-03 02:11 采纳率: 100%
浏览 51
已结题

还没有睡着的各位OIer给个思路行嘛Q^Q

img


题目描述
给一个整数n,在1~n之间有多少整数不能表示为pow( a ,b )(a 的b 次幂)的形式,其中a,b不小于2.

数据范围:1<=n<=10^10

vickyの opinion:
一开始我想的是遍历每个数,但后面我发现这个数据范围直接out掉了遍历,遍历2.5*10^7就已经1s了,更何况遍历10^10次呢 QAQ
随后我便开始猜想其中是否有什么规律,但是在考场找了一个多小时的规律,回家又找了半个小时,啥也没找到……
求思路Q^Q

  • 写回答

3条回答 默认 最新

  • SmallAntJ 2022-05-03 04:53
    关注

    1、首先a的b次幂,b>=2的话,底数a的范围就是在 [2, 根号N] 之间的整数,所以只要遍历这些底数,大概是10的5次方。
    2、其次a的b次幂要小于等于N,那么对于每一个底数a,指数b的范围就是在 [2,log(N)/log(a)] 之间的整数,这里不需要遍历,可以直接求出满足条件的数的个数 floor( log(N)/log(a) - 2 +1)。
    3、用 N减去满足条件的数的个数,就得到你想要的结果了。

    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论 编辑记录
查看更多回答(2条)

报告相同问题?

问题事件

  • 系统已结题 5月11日
  • 已采纳回答 5月3日
  • 创建了问题 5月3日

悬赏问题

  • ¥15 关于#web项目#的问题,请各位专家解答!
  • ¥15 vmtools环境不正常
  • ¥15 请问如何在Ubuntu系统中安装使用microsoft R open?
  • ¥15 jupyter notebook
  • ¥30 informer时间序列预测
  • ¥20 SSR引物多态性分析
  • ¥15 大漠插件在Win11易语言注册调用和免注册灵异事件,VS上注册调用完全没问题
  • ¥15 Addressable缓存机制做热更新的问题
  • ¥15 微信开发者工具vant组件
  • ¥15 iPhone iCloud云盘资料删除,MAC丢失50多G桌面资料