UVA11526H(n)（整除分块）

题目链接 https://cn.vjudge.net/problem/UVA-11526

【题意】
输入一个整数 nn (int范围内) 求下面式子的值

【思路】
直接计算的复杂度是O(n)O(n)的&＃xff0c;不满足要求&＃xff0c;但是可以利用整数分块优化到O(n−−√)O(n)&＃xff0c;打个表可以发现其实⌊ni⌋⌊ni⌋ 的值是呈现一个块状分布的&＃xff0c;如果最左边的下标为L&＃xff0c;那么右边的下标R刚好是n/(n/L)&＃xff0c;根据这一点来计算即可

#include
using namespace std;
typedef long long ll;int main(){int T;scanf("%d",&T);while(T--){ll n;scanf("%lld",&n);ll ans&＃61;0;for(ll L&＃61;1,R;L<&＃61;n;L&＃61;R&＃43;1){R&＃61;n/(n/L);ans&＃43;&＃61;(R-L&＃43;1)*(n/L);}printf("%lld\n",ans);}return 0;
}