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

「模板」整除分块
bfw LV 9 MOD @ 2020-08-02 14:30:45

数据范围扩增到 \(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 @ 2020-08-02 18:47:49
经测试，线性做法可以被卡成 \(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;
 } 
```
所以既然能卡掉就不加强数据了吧？（出题人懒（（（
- bfw LV 9 MOD @ 2020-08-02 21:42:30
  
  嗯不错，但是最好标明部分分
- oistream (oistream) LV 8 MOD @ 2020-08-03 17:18:08
  
  @bfw:
  
  \(\mathcal{FIXED.}\)，昨天可能有点晕...想着要标部分分结果给忘了...
oistream (oistream) LV 8 MOD @ 2020-08-02 18:08:42
统一按序回复：
1. 个人觉得 \(10^9\) 能卡掉线性？容我写个暴力试试。
2. 刚才查了一下，关于此算法确实也有叫 整除分块 的，这种叫法也确实更科学，因此可改名。
3. 目前数据包含极限样例（\(n=10^9\) 左右）。关于 \(10^{12}\) 的样例，见 A1。
4. 部分分也是有的，具体分数也得等我测一下。同时我在题目里增加了对部分分的说明。
感谢您改题前的说明，我今天也会抽时间加强一下数据。

ID

1100

难度

5

分类

分块、数论点击显示

标签

递交数

已通过

2

通过率

50%

被复制

1

上传者

oistream (oistream)