Advertisement
SorahISA

I. I Like Short Statements

Sep 25th, 2024
89
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.01 KB | Source Code | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. using i64 = int64_t;
  5. using i128 = __int128;
  6.  
  7. int main() {
  8.     ios_base::sync_with_stdio(0), cin.tie(0);
  9.    
  10.     i64 N, M; cin >> N >> M;
  11.    
  12.     /// f(x) - f(x-1) = 2x-1 - sigma_1(x) ///
  13.    
  14.     auto f = [&](i128 x) -> i128 {
  15.         /// find sum of (x mod i) = x - (x / i) * i ///
  16.        
  17.         i128 ans = x * x, i = 1;
  18.         while (i <= x) {
  19.             /// [x/j == x/i] --> [(x+1)/(x/i) < j <= x/(x/i)] ///
  20.             i128 r = min(x / (x / i), x);
  21.             ans -= (x / i) * (i + r) * (r - i + 1) / 2;
  22.             i = r + 1;
  23.         }
  24.         return ans;
  25.     };
  26.    
  27.     i64 lo = 0, hi = N, mi;
  28.     while (lo < hi) {
  29.         mi = (lo + hi + 1) >> 1;
  30.         if (f(mi) <= M) lo = mi;
  31.         else            hi = mi - 1;
  32.     }
  33.    
  34.     i64 ans = lo;
  35.     for (int d = 1; d <= 5; ++d) {
  36.         if (lo + d <= N and f(lo+d) <= M) ++ans;
  37.         if (lo - d >= 1 and f(lo-d) >  M) --ans;
  38.     }
  39.     cout << ans << "\n";
  40.    
  41.     return 0;
  42. }
  43.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement