Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <set>
- #include <vector>
- #include <algorithm>
- #include <map>
- #include <cassert>
- #include <cstdlib>
- using namespace std;
- typedef int64_t Int;
- const Int mod = (Int)1e9+7;
- Int solveSlow(Int n, Int m) {
- Int answ = 0;
- for (Int i = 1; i <= m; ++i) {
- (answ += n % i) %= mod;
- }
- return answ;
- }
- Int sum(Int a, Int b) {
- Int len = b - a + 1;
- return ((a % mod) * (len % mod) + (len * (len-1) / 2) % mod) % mod;
- }
- Int solveFast(Int n, Int m) {
- Int answ = (n % mod) * (std::max(Int(0), m - n) % mod) % mod;
- // std::cout << answ << std::endl;
- Int last = n-1;
- for (Int i = 1; last * last > n; ++i) {
- Int r = std::min(n / i, m);
- Int l = n / (i+1);
- if (r < l) continue;
- Int curr = i % mod * sum(0, r - l - 1) % mod + (r - l) % mod * (n % i) % mod;
- answ += curr;
- last = n / (i+1);
- std::cout << "last = " << last << ", curr = " << curr << std::endl;
- }
- for (Int i = 1; i <= last; ++i) {
- (answ += n % i) %= mod;
- }
- return answ;
- }
- void test() {
- for (Int n = 1; n <= 10; ++n) {
- for (Int m = 1; m <= 10; ++m) {
- if (solveFast(n, m) != solveSlow(n, m)) {
- std::cout << "n = " << n << ", m = " << m << std::endl;
- }
- }
- }
- std::exit(0);
- }
- int main()
- {
- //test();
- //freopen("input.txt", "rt", stdin);
- ios_base::sync_with_stdio(false);
- cin.tie(0);
- cout.tie(0);
- Int n, m; std::cin >> n >> m;
- std::cout << solveFast(n, m) << std::endl;
- std::cout << solveSlow(n, m) << std::endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement