Dang_Quan_10_Tin

SUMDIV

Sep 22nd, 2021 (edited)
484
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #define task "SUMDIV"
  2.  
  3. #include <iostream>
  4. #include <cstdio>
  5. #include <vector>
  6. #include <algorithm>
  7.  
  8. using namespace std;
  9.  
  10. using ll = long long;
  11.  
  12. constexpr int N = 1e5 + 5;
  13. int l, r;
  14. vector<int> divisors;
  15.  
  16. void Read()
  17. {
  18.     cin >> l >> r;
  19. }
  20.  
  21. void Sub_12()
  22. {
  23.     for (; l <= r; ++l)
  24.         for (int i = 1; i * i <= l; ++i)
  25.             if (l % i == 0)
  26.             {
  27.                 divisors.emplace_back(i);
  28.                 divisors.emplace_back(l / i);
  29.             }
  30.  
  31.     sort(divisors.begin(), divisors.end());
  32.     divisors.resize(unique(divisors.begin(), divisors.end()) - divisors.begin());
  33.  
  34.     ll ans(0);
  35.  
  36.     for (auto i : divisors)
  37.         ans += i;
  38.  
  39.     cout << ans;
  40. }
  41.  
  42. void Sub_3()
  43. {
  44.     ll ans(0);
  45.  
  46.     for (int i = 1; i <= r; ++i)
  47.         if ((l + i - 1) / i <= r / i)
  48.             ans += i;
  49.  
  50.     cout << ans;
  51. }
  52.  
  53. ll GetSum(ll l, ll r)
  54. {
  55.     if (l > r)
  56.         return 0;
  57.     return (r - l + 1) * (r + l) / 2;
  58. }
  59.  
  60. void Sub_4()
  61. {
  62.  
  63.     ll ans(0);
  64.  
  65.     vector<pair<int, int>> intervals;
  66.  
  67.     for (int i = 1; i * i <= r; ++i)
  68.         if ((l + i - 1) / i <= r / i)
  69.         {
  70.             intervals.emplace_back(i, i);
  71.             intervals.emplace_back((l + i - 1) / i, r / i);
  72.         }
  73.  
  74.     sort(intervals.begin(), intervals.end());
  75.  
  76.     for (int i = 0, j = 0; i < (int)intervals.size(); ++i)
  77.     {
  78.         j = max(j, intervals[i].first);
  79.         ans += GetSum(j, intervals[i].second);
  80.         j = max(j, intervals[i].second + 1);
  81.     }
  82.  
  83.     cout << ans;
  84. }
  85.  
  86. int32_t main()
  87. {
  88.     ios::sync_with_stdio(0);
  89.     cin.tie(0);
  90.     cout.tie(0);
  91.     if (fopen(task ".INP", "r"))
  92.     {
  93.         freopen(task ".INP", "r", stdin);
  94.         freopen(task ".OUT", "w", stdout);
  95.     }
  96.     Read();
  97.     if (r <= 1000 || r - l <= 1000)
  98.         Sub_12();
  99.     else if (r <= 1e6)
  100.         Sub_3();
  101.     else
  102.     Sub_4();
  103. }
  104.  
RAW Paste Data