首页 > 代码库 > 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)(简单数论)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。