UVa 11526 H(n)

题意:

long long H(int n){
  long long res = 0;
  for( int i = 1; i <= n; i=i+1 ){
    res = (res + n/i);
  }
  return res;
}

求这样一个函数的值。

分析:

这个题很像我做莫比乌斯反演时的一个分块加速的优化。

注意到n/i的整数部分,有许多重复的数。具体一点,对于某一个i,在区间[i, n / (n / i)]中n/i的值是一样的。

例如在[17, 20]中的i,100/i的值都是5.

 #include <iostream>
#include <cstdio>
using namespace std; int main()
{
int T;
long long n;
scanf("%d", &T);
while(T--)
{
scanf("%lld", &n);
long long ans = ;
for(long long i = , j; i <= n; i = j+)
{
j = n / (n / i);
if(j > n) j = n;
ans += (j-i+) * (n/i);
}
printf("%lld\n", ans);
} return ;
}

代码君

找到一份更快的代码,但是题解看得十分不懂,一头雾水,=_=||

UVa 11526 H(n) (数论)

上一篇:GDB调试方法精粹


下一篇:Nginx【第一篇】安装