Advertisement
dmkozyrev

Untitled

May 3rd, 2018
95
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.41 KB | None | 0 0
  1. #include <iostream>
  2. #include <set>
  3. #include <vector>
  4. #include <algorithm>
  5. #include <map>
  6. #include <cassert>
  7. #include <cstdlib>
  8. using namespace std;
  9.  
  10. typedef int64_t Int;
  11.  
  12. const Int mod = (Int)1e9+7;
  13.  
  14. Int solveSlow(Int n, Int m) {
  15.     Int answ = 0;
  16.     for (Int i = 1; i <= m; ++i) {
  17.         (answ += n % i) %= mod;
  18.     }
  19.     return answ;
  20. }
  21.  
  22. Int sum(Int a, Int b) {
  23.     Int len = b - a + 1;
  24.     return ((a % mod) * (len % mod) + (len * (len-1) / 2) % mod) % mod;
  25. }
  26.  
  27.  
  28.  
  29. Int solveFast(Int n, Int m) {
  30.     Int answ = (n % mod) * (std::max(Int(0), m - n) % mod) % mod;
  31. //  std::cout << answ << std::endl;
  32.     Int last = n-1;
  33.     for (Int i = 1; last * last > n; ++i) {
  34.         Int r = std::min(n / i, m);
  35.         Int l = n / (i+1);
  36.         if (r < l) continue;
  37.         Int curr = i % mod * sum(0, r - l - 1) % mod + (r - l) % mod * (n % i) % mod;
  38.         answ += curr;
  39.         last = n / (i+1);
  40.         std::cout << "last = " << last << ", curr = " << curr << std::endl;
  41.     }
  42.    
  43.     for (Int i = 1; i <= last; ++i) {
  44.         (answ += n % i) %= mod;
  45.     }
  46.     return answ;
  47. }
  48.  
  49. void test() {
  50.     for (Int n = 1; n <= 10; ++n) {
  51.         for (Int m = 1; m <= 10; ++m) {
  52.             if (solveFast(n, m) != solveSlow(n, m)) {
  53.                 std::cout << "n = " << n << ", m = " << m << std::endl;
  54.             }
  55.         }
  56.     }
  57.     std::exit(0);
  58. }
  59.  
  60. int main()
  61. {
  62.     //test();
  63.     //freopen("input.txt", "rt", stdin);
  64.     ios_base::sync_with_stdio(false);
  65.     cin.tie(0);
  66.     cout.tie(0);
  67.     Int n, m; std::cin >> n >> m;
  68.     std::cout << solveFast(n, m) << std::endl;
  69.     std::cout << solveSlow(n, m) << std::endl;
  70.     return 0;
  71. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement