fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std; 
  3.  
  4. typedef long long ll; 
  5.  
  6. const int N = (int)1e6 + 5; 
  7.  
  8. ll cnt[N], sum[N]; 
  9.  
  10. void sieve() {
  11. 	for (int i = 1; i < N; i++) { // O(NlogN)
  12. 		// j bổ sung i làm ước
  13. 		for (int j = i; j < N; j += i) cnt[j] += 1, sum[j] += i; 
  14. 	}
  15.  
  16. 	for (int i = 2; i < N; i++) { // O(N)
  17. 		cnt[i] += cnt[i - 1]; 
  18. 		sum[i] += sum[i - 1]; 
  19. 	}
  20. 	// O(NlogN + N)
  21. }
  22.  
  23. // a[5] =     {1, 2, 3, 4, 5}
  24. // sum[] ={0, 1, 3, 6, 10, 15} // O(N)
  25. // sum[i] là tổng các phần tử từ 1 đến i trên mảng a 
  26.  
  27. // lấy tổng trong đoạn [L, R] = sum[R] - sum[L - 1] // O(1)
  28.  
  29. int main() {
  30. 	ios::sync_with_stdio(0); 
  31. 	cin.tie(0); 
  32. 	int T; cin >> T; 
  33.  
  34. 	sieve(); // O(NlogN)
  35.  
  36. 	while (T--) {
  37. 		int x, y; 
  38. 		cin >> x >> y; 
  39. 		ll cnt_div = cnt[y] - cnt[x - 1]; // O(1)
  40. 		ll sum_div = sum[y] - sum[x - 1]; // O(1)
  41.  
  42. 		cout << cnt_div << ' ' << sum_div << '\n'; 
  43. 	} // O(T)
  44.  
  45. 	// O(NlogN + N + T)
  46. }
  47.  
Success #stdin #stdout 0.16s 19204KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/j32poW
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!