?
# | Author | Problem | Lang | Verdict | Time | Memory | Sent | Judged | |
---|---|---|---|---|---|---|---|---|---|
157507503 |
Practice: Hunny_Bunny |
546D - 29 | C++17 (GCC 9-64) | Time limit exceeded on test 5 | 3000 ms | 64796 KB | 2022-05-17 21:42:39 | 2022-05-17 21:42:39 |
#include <iostream> #include <bits/stdc++.h> #include <map> #include <list> #include <utility> #include <algorithm> #include <vector> #define INF 10000000000 #define ll long long int #define pb push_back #define mp make_pair #define FOR(i, n) for (int i = 0; i < n; i++) #define FORR(i, a, b) for (int i = a; i < b; i++) using namespace std; bool isprime[5000009]; int dp[5000009], minfact[5000009]; int fact[5000009]; // sum of factors of factorial till i void sieve_fun() { for (int i = 0; i < 5000009; i++) { isprime[i] = true; } isprime[0] = isprime[1] = false; minfact[0] = 0; minfact[1] = 0; minfact[2] = 2; for (int i = 3; i < 5000009; i += 2) { if (isprime[i] == true) { minfact[i] = i; for (int j = i; (((ll)j) * ((ll)i)) < 5000009; j += 2) { isprime[i * j] = false; minfact[i * j] = i; } } } return; } void dp_fun() // dp will store sum of prime factors of num { for (int i = 2; i < 5000009; i++) { if (i % 2 == 0) { dp[i] = dp[i / 2] + 1; } else { dp[i] = dp[i / minfact[i]] + 1; } } } int main() { ios::sync_with_stdio(false); cin.tie(NULL); sieve_fun(); int t; cin >> t; memset(dp, -1, sizeof(dp)); dp[1] = 0, dp[0] = 0; dp_fun(); fact[0] = fact[1] = 0; for (int i = 2; i < 5000009; i++) { fact[i] = fact[i - 1] + dp[i]; } FOR(j, t) { int a, b; cin >> a >> b; cout << fact[a] - fact[b] << endl; } return 0; }
?
?
?
?