UVa-11526 : H(n)
問題概要
N(<2^31)が与えられる。sum N/iを求める問題。
解法
即数列検索。O(sqrt(N))で求められるらしい。テストケースが1000個と多くて微妙に不安になるけど何とか通った。
acceptされたコード
計算量O(sqrt(N))。
#include <cstdio> #include <cmath> using namespace std; typedef long long int64; int N; int64 sq(int64 x){ return x*x; } int64 solve(){ if(N <= 0){ return 0; } int64 ans = 0; for(int i=1, st=sqrt(N); i<=st; i++){ ans += N / i; } ans = 2*ans - sq((int)sqrt(N)); return ans; } int main(){ int T; scanf("%d", &T); while(T--){ scanf("%d", &N); printf("%lld\n", solve()); } return 0; }