【AtCoder】計算量の見積り

例題1

ABC227C - ABC conjecture

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
  ll N; cin >> N;
  
  ll ans = 0;
  for (ll a = 1; a*a*a <= N; a++) {
    for (ll b = a; a*b*b <= N; b++) {
      ll mc = N / (a*b);
      ans += mc - b + 1;
    }
  }
  
  cout << ans << endl;
}

\displaylines{
\sum_{n=1}^{\sqrt[3]{N}} (\sqrt{\frac{N}{a}} - a + 1) 
\leq \sqrt{N} + \int_{1}^{\sqrt[3]{N}} (\sqrt{\frac{N}{x}} - x + 1)dx
= O(N^{\frac{2}{3}}) \\
i.e. \sum_{n=1}^{\sqrt[3]{N}} (\sqrt{\frac{N}{a}} - a + 1)
\leq O(N^{\frac{2}{3}})
}