【Fixed】提出以下建议 - 7FOJ - Vijos

「模板」整除分块
bfw LV 9 MOD @ 4 年前

数据范围扩增到 $1 \leq n \leq 10^{14}$ 或 $1 \leq n \leq 10^{15}$ ，一定程度上 这也是复杂度的暗示。
“除法分块” 改为 “整除分块” 较为合适。
加两个大样例：一个是 $n = 10^8$ 左右的，用来检验线性复杂度；一个是 $n = 10^{12}$ 左右的，用来检验正解。
设亿点点部分分，给线性 $30$ 分之类， $10^9$ 开成 $60$ 分。具体情况可以视情节调整。

当然我是可以自己直接改题面的，但是至少别人的题改了还是要 申请说明一下 吧。

oistream (oistream) LV 8 MOD @ 4 年前
经测试，线性做法可以被卡成 $60$ 分。如下是测试记录：https://vijos.org/d/oistream/records/5f26998bf4136203a291d013

代码：
#include <iostream> using namespace std; typedef long long Num; int main() { Num n,sum=0; cin>>n; for(Num i=1ll;i<=n;i++) { sum+=n/i; } cout<<sum<<endl; return 0; }
Copy
所以既然能卡掉就不加强数据了吧？（出题人懒（（（
- bfw LV 9 MOD @ 4 年前
  
  嗯不错，但是最好标明部分分
- oistream (oistream) LV 8 MOD @ 4 年前
  
  @bfw:
  
  $\mathcal{FIXED.}$ ，昨天可能有点晕...想着要标部分分结果给忘了...
oistream (oistream) LV 8 MOD @ 4 年前
统一按序回复：
1. 个人觉得 $10^9$ 能卡掉线性？容我写个暴力试试。
2. 刚才查了一下，关于此算法确实也有叫 整除分块 的，这种叫法也确实更科学，因此可改名。
3. 目前数据包含极限样例（ $n=10^9$ 左右）。关于 $10^{12}$ 的样例，见 A1。
4. 部分分也是有的，具体分数也得等我测一下。同时我在题目里增加了对部分分的说明。
感谢您改题前的说明，我今天也会抽时间加强一下数据。

ID

1100

难度

5

分类

分块、数论点击显示

标签

递交数

已通过

2

通过率

50%

被复制

1

上传者

oistream (oistream)