AtCoder abc230_e
AtCoder abc230_e Fraction Floor Sum
求:
\[\sum_{i = 1}^N ⌊\dfrac{N}{i}⌋
\]
P2261 [CQOI2007]余数求和
\[G(n, k) = \sum_{i = 1}^n k \bmod i = \sum_{i = 1}^n (k - i \times⌊\dfrac{k}{i} ⌋) = n \times k - \sum_{i = 1}^n i \times⌊\dfrac{k}{i}⌋
\]
发现$\sum_{i = 1}^n i \times⌊\dfrac{k}{i}⌋ $可以数论分块来做
ll n, k;
void solve()
{
cin>>n>>k;
ll res = n * k;
for(ll l = 1; l <= n; l++)
{
ll d = k / l, r;
if(d == 0)
r = n;
else
r = min(n, k / d);
ll m = r - l + 1;
res -= d * (l + r) * m / 2;
l = r;
}
cout<<res<<endl;
}