fork download 
  1. #include <bits/stdc++.h> 
  2. using namespace std;  
  3.  
  4. typedef long long ll;  
  5. typedef pair<int, int> ii;  
  6.  
  7. const int INF = 1e9;  
  8. const ll LINF = 1e18;  
  9.  
  10. const int MOD = 1e9 + 7; 
  11.  
  12. ll mul(ll a, ll b) {
  13. 	return ((a % MOD) * (b % MOD)) % MOD; 
  14. }
  15.  
  16. ll add(ll a, ll b) {
  17. 	return (a + b) % MOD; 
  18. }
  19.  
  20. ll binpow(ll a, ll b) {
  21. 	ll ans = 1; 
  22. 	for (; b > 0; b >>= 1) {
  23. 		if (b & 1) ans = ans * a % MOD; 
  24. 		a = a * a % MOD; 
  25. 	}
  26. 	return ans; 
  27. }
  28.  
  29. int main() {
  30. 	ios::sync_with_stdio(0); cin.tie(0);  	
  31. 	ll n;   
  32. 	cin >> n; 
  33.  
  34. 	ll inv_two = binpow(2, MOD - 2); // nghịch đảo modulo của 2 
  35. 	ll l = 1, ans = 0;  
  36.  
  37. 	while (l <= n) {
  38. 		ll k = n / l;  
  39. 		ll r = n / k;   
  40.  
  41. 		// Với i thuộc đoạn [l, r] thì ta có floor(n / i) = k
  42. 		//     l * k + (l + 1) * k + ... + r * k 
  43. 		//   = k * [(r + l) * (r - l + 1) / 2]
  44. 		ll sum = mul(mul(r + l, r - l + 1), inv_two); 
  45. 		sum = mul(k, sum); 
  46. 		ans = add(ans, sum);   
  47.  
  48. 		l = r + 1; 
  49. 	}
  50.  
  51. 	cout << ans << '\n'; 
  52. }
Success #stdin #stdout 0.01s 5276KB
comments (?)
stdin 
5
stdout 
21
https://ideone.com/Wd5mRr
language:
C++14 (gcc 8.3)
created:
1 year 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!