| 题目名称 | 2664. 等比数列计数 |
|---|---|
| 输入输出 | seq_count.in/out |
| 难度等级 | ★★★★ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 256 MiB |
| 测试数据 | 10 |
| 题目来源 |
 FoolMike
于2017-04-18加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：9， 提交：25， 通过率：36% | ||||
 梦那边的美好ET |
100 | 1.081 s | 127.13 MiB | C++ |
 FoolMike |
100 | 1.214 s | 126.23 MiB | C++ |
|
梦那边的美好ET |
100 | 1.324 s | 127.13 MiB | C++ |
 6666 |
100 | 1.655 s | 80.40 MiB | C++ |
|
_Itachi |
100 | 2.289 s | 80.40 MiB | C++ |
|
_Itachi |
100 | 2.339 s | 80.40 MiB | C++ |
 小一米 |
100 | 2.768 s | 51.79 MiB | C++ |
 光明正大 |
100 | 2.812 s | 166.25 MiB | C++ |
 MistyEye |
100 | 3.204 s | 95.68 MiB | C++ |
|
_Itachi |
90 | 7.829 s | 80.40 MiB | C++ |
| 关于 等比数列计数 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
回复 @FoolMike :
哇，好强啊！！ 跑了下10^14我的算法跑了19999999次，您的只跑了87719次，简直高明到不知道哪里去了！ UPD：又试了几个数据，发现您的计算次数是n^(1/3)级别的（否则怎么可能10^7*cmath::sqrt()跑得过1s呢！ _Itachi
2017-04-19 06:37
6楼
| ||||
|
回复 @FoolMike :
预处理是sqrt(n)的，不过应该比计算结果的还快，毕竟cmath::sqrt()不能当成O(1)的 _Itachi
2017-04-19 06:36
5楼
| ||||
|
回复 @_Itachi :
预处理的复杂度呢？难道不是O(sqrt(n))的吗？ FoolMike
2017-04-18 20:50
4楼
| ||||
|
回复 @_Itachi :
因为求sqrt太慢了……所以需要一点小优化。 | ||||
|
明明我写的也是sqrt(n)的，为什么被卡常了。。
_Itachi
2017-04-18 19:44
2楼
| ||||
|
没数据（我才不会说我只是交个n^(5/3)的大暴力骗数据呢！）
6666
2017-04-18 19:07
1楼
| ||||