lightoj 1245 Harmonic Number (II)（简单数论）

题目链接：http://www.lightoj.com/volume_showproblem.php?problem=1245

题意：求f(n)=n/1+n/2.....n/n,其中n/i保留整数

显然一眼看不出什么规律。而且n有2e31直接暴力肯定要出事情

但是f=n/x这个函数很好关于y = x 对称对称点刚好是sqrt(n)

于是就简单了直接求sum+n/i (i*i<n && i >=1)

然后乘以2，再减去i*i即可。

这个i*i表示的是什么呢，由于对称上半部份的值完全可以平移下来再减去i个i（这时候的i是临界于sqrt(n)整数点）

#include <iostream>

#include <cstring>

#include <string>

#include <cstdio>

#include <cmath>

using namespace std;

int main() {

    int t , ans = 0;

    long long n;

    scanf("%d" , &t);

    while(t--) {

        ans++;

        scanf("%lld" , &n);

        long long sum = 0;

        int i;

        for(i = 1 ; (long long)i * i <= n ; i++)

            sum += n / i;

        sum *= 2;

        sum -= (i - 1) * (i - 1);

        printf("Case %d: %lld\n" , ans , sum);

    }

    return 0;

}

巴特西

lightoj 1245 Harmonic Number (II)（简单数论）

最新文章

热门文章