首页 > 代码库 > lightoj 1245 Harmonic Number (II)(简单数论)

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)(简单数论)