fork download 
  1. /*******************************************************
  2. 4) AtCoder — Count ordered triplets (a,b,c) in 1..n
  3. such that a % b = c and a,b,c are pairwise distinct.
  4.  
  5. Approach used - the classic O(sqrt(n)) "group by n / i" trick.
  6.  
  7. Key idea (even simpler counting):
  8. - For a % b = c with c >= 1:
  9.     * If a < b  => a % b = a  => c = a  => not distinct (a == c) ❌
  10.     * So we must have a >= b (i.e., quotient q >= 1).
  11. - For fixed b (b >= 2):
  12.     * valid a are b..n
  13.     * c = a % b must be non-zero (else c=0 not allowed)
  14.     => count(b) = (number of a in [b..n]) - (number of multiples of b in [b..n])
  15.  
  16. Compute:
  17. - number of a in [b..n] = n - b + 1
  18. - number of multiples of b in [1..n] = floor(n/b)
  19.   (and all of them are >= b, so same count in [b..n])
  20. So:
  21.     count(b) = (n - b + 1) - floor(n/b)
  22.  
  23. Total answer:
  24.     ans = sum_{b=2..n} (n - b + 1) - sum_{b=2..n} floor(n/b)
  25.  
  26. First sum is easy:
  27.     sum_{b=2..n} (n - b + 1) = 1 + 2 + ... + (n-1) = n(n-1)/2
  28.  
  29. Let H(n) = sum_{i=1..n} floor(n/i)
  30. Then sum_{b=2..n} floor(n/b) = H(n) - floor(n/1) = H(n) - n
  31.  
  32. So:
  33.     ans = n(n-1)/2 - (H(n) - n) = n(n+1)/2 - H(n)
  34.  
  35. Now compute H(n) in O(sqrt(n)) by grouping indices where floor(n/i) is constant.
  36.  
  37. Time: O(sqrt(n))
  38. *******************************************************/
  39.  
  40. #include <bits/stdc++.h>                      // include all common C++ headers
  41. using namespace std;                          // avoid writing std:: everywhere
  42.  
  43. static void print_int128(__int128 x) {        // helper: print big __int128 safely
  44.     if (x == 0) {                             // if number is zero
  45.         cout << 0;                            // print 0
  46.         return;                               // and return
  47.     }
  48.     if (x < 0) {                              // if negative (not expected here, but safe)
  49.         cout << '-';                          // print minus sign
  50.         x = -x;                               // make it positive
  51.     }
  52.     string s;                                 // we'll build digits here
  53.     while (x > 0) {                           // while digits remain
  54.         int digit = (int)(x % 10);            // take last digit
  55.         s.push_back(char('0' + digit));       // append it
  56.         x /= 10;                              // remove last digit
  57.     }
  58.     reverse(s.begin(), s.end());              // digits were reversed, fix order
  59.     cout << s;                                // print final string
  60. }
  61.  
  62. int main() {                                  // program starts here
  63.     ios::sync_with_stdio(false);              // fast input/output
  64.     cin.tie(nullptr);                         // untie cin from cout for speed
  65.  
  66.     long long n;                              // read n (can be large)
  67.     cin >> n;                                 // input n
  68.  
  69.     // Compute H(n) = sum_{i=1..n} floor(n/i) in O(sqrt(n))
  70.     __int128 H = 0;                           // H can be large, use __int128
  71.     long long l = 1;                          // l = start of current block
  72.  
  73.     while (l <= n) {                          // process until we cover all i from 1..n
  74.         long long q = n / l;                  // q = floor(n/l) (constant inside this block)
  75.         long long r = n / q;                  // r = largest i such that floor(n/i) == q
  76.         H += (__int128)q * (r - l + 1);       // add q repeated (r-l+1) times
  77.         l = r + 1;                            // move to next block
  78.     }
  79.  
  80.     // ans = n(n+1)/2 - H(n)
  81.     __int128 nn = (__int128)n;                // cast n to __int128 once
  82.     __int128 totalPairs = nn * (nn + 1) / 2;  // compute n(n+1)/2 safely
  83.     __int128 ans = totalPairs - H;            // final answer
  84.  
  85.     print_int128(ans);                        // print answer (supports huge values)
  86.     cout << "\n";                             // newline
  87.     return 0;                                 // done
  88. }
Success #stdin #stdout 0.31s 5292KB
comments (?)
stdin 
Standard input is empty
stdout 
266111194612608166957462543
https://ideone.com/WfVDl1
language:
C++14 (gcc 8.3)
created:
117 days ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!