[AHOI 2005] 约数研究

知识点

数论、约数、计数、整除分块

解题思路

约数d在1到n中恰好出现floor(n/d)次，因此答案为sum floor(n/d)。对左端点l，令q=n/l，则商为q的最后位置为r=n/q，一次累加q*(r-l+1)，再令l=r+1。

正确性说明

每对正整数(d,x)且d整除x都贡献一次，按x统计得到原式，按d统计得到新式。floor(n/d)在区间[l,n/floor(n/l)]内不变，故分块累加与逐项求和等价。

易错点

分块右端点是n/q；下一块从r+1开始；n=1有答案1；乘法和累加使用long long。

复杂度

整除商只有O(sqrt n)种，时间O(sqrt n)，额外空间O(1)。

参考代码（GNU C++17）

#include<bits/stdc++.h>
using namespace std;
int main(){long long n;cin>>n;long long ans=0;for(long long l=1,r;l<=n;l=r+1){long long q=n/l;r=n/q;ans+=q*(r-l+1);}cout<<ans<<'\n';}