E - Fraction Floor Sum 解説 by en_translator
Note that \(1\leq \left[ \frac{N}{i} \right] \leq N\) for every \(1\leq i\leq N\).
Let \(k_0= [\sqrt{N}]\).
For each \(k=1,2,\ldots,k_0\),
consider the number of \(i\) such that \( \left[ \frac{N}{i} \right]=k\).
\(\left[ \frac{N}{i} \right]=k\), that is, \(k\leq \frac{N}{i}<k+1\),
is equivalent to \(\frac{N}{k+1}<i\leq \frac{N}{k}\). The number of integers \(i\) that satisfy this this is \(\left( \left[ \frac{N}{k} \right]-\left[ \frac{N}{k+1} \right]\right) \).
Next, consider the other case; i.e. when \(\left[ \frac{N}{i} \right]\geq k_0+1\).
In that case, \(\frac{N}{i}\geq k_0+1\), so \(i\leq \frac{N}{k_0+1}<\sqrt{N}\), and there are at most \(\sqrt{N}\) number of such positive integers \(i\), so they can be summed up one by one.
Therefore, the answer is expressed as
\[ \sum_{k=1}^{k_0} \left( \left( \left[ \frac{N}{k} \right]-\left[ \frac{N}{k+1} \right]\right) \times k\right)+ \sum_{i=1}^{\left[ \frac{N}{k_0+1} \right]} \left[ \frac{N}{i} \right], \]
and each of the two terms can be computed in an \(O(\sqrt{N})\), so the problem has been solved.
Sample code in C++:
#include <bits/stdc++.h>
using namespace std;
int main(void) {
long long n, ans, k;
cin >> n;
for (long long i = 1; i <= n; i++) {
if (i*i <= n)k = i;
else break;
}
ans = 0;
for (long long i = 1; i <= k; i++)ans += ((n / i) - (n / (i + 1)))*i;
for (long long i = 1; i <= n / (k + 1); i++)ans += (n / i);
cout << ans << endl;
return 0;
}
投稿日時:
最終更新: