当前位置: 代码迷 >> 综合 >> LightOJ - 1245 Harmonic Number (II)(数论分块)
  详细解决方案

LightOJ - 1245 Harmonic Number (II)(数论分块)

热度:26   发布时间:2023-12-09 20:17:23.0

链接:LightOJ - 1245 Harmonic Number (II)

题意:

给出 T ( ≤ 1000 ) T(\le1000) T(1000) n ( 1 ≤ n ≤ 2 31 ) n(1\le n\le2^{31}) n(1n231),每次求解 H ( n ) = ? n 1 ? + ? n 2 ? + ? + ? n n ? H(n)=\lfloor \frac{n}{1}\rfloor+\lfloor\frac{n}{2}\rfloor+\dots+\lfloor\frac{n}{n}\rfloor H(n)=?1n??+?2n??+?+?nn??



分析:

对于 ? n i ? \lfloor \frac{n}{i}\rfloor ?in??求和,实际上 ? n i ? \lfloor \frac{n}{i}\rfloor ?in??只有至多 ? 2 n ? \lfloor 2\sqrt n\rfloor ?2n ??种取值。

对于任意 i ≤ n i\le n in,需要找到一个最大的 j ≤ n j\le n jn,使得 ? n i ? = ? n j ? \lfloor \frac{n}{i}\rfloor=\lfloor \frac{n}{j}\rfloor ?in??=?jn??,则有:
j = ? n ? n i ? ? j=\left\lfloor \frac{n}{\lfloor \frac{n}{i}\rfloor}\right \rfloor j=??in??n??

所以当从小到大枚举 i i i,则 ? n i ? \lfloor \frac{n}{i}\rfloor ?in??的个数为 j ? i + 1 j-i+1 j?i+1个,求和的时间复杂度为 O ( ? 2 n ? ) O(\lfloor 2\sqrt n\rfloor) O(?2n ??)



以下代码:

#include<bits/stdc++.h>
#define LL long long
using namespace std;
int main()
{
    int T,kase=0;scanf("%d",&T);LL n;while(T--){
    scanf("%lld",&n);LL i=1,j,ans=0;while(i<=n){
    j=n/(n/i);ans+=(n/i)*(j-i+1);i=j+1;}printf("Case %d: %lld\n",++kase,ans);}return 0;
}
  相关解决方案