# |
Author |
Problem |
Lang |
Verdict |
Time |
Memory |
Sent |
Judged |
|
213448834 |
Practice:
Kuber |
546D
- 29
|
C++14 (GCC 6-32)
|
Time limit exceeded on test 3
|
3000 ms
|
86116 KB
|
2023-07-12 06:50:01 |
2023-07-12 06:50:01 |
|
#include <bits/stdc++.h>
#include <cstdint>
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll, ll> pi;
#define PB push_back
#define MP make_pair
#define FOR for(long long i = 0;i<n;i++)
#define SP << " " <<
#define F first
#define S second
#define MOD 1000000007
#define max_n 5000005
#define lMOD 1e16
int a1[1000005], b1[1000005];
int n;
ll p[max_n];
ll f[max_n];
void solve(){
cin >> n;
FOR cin >> a1[i] >> b1[i];
for(int i = 2; i<5000001; i++){
if (f[i]!=0) continue; f[i] = 1;
for(int j = 2*i; j<5000001; j+=i){
ll te = j;
while(te%i ==0){
te/=i;
f[j]++;
}
}
}
p[0] = 0;
for(int i = 1; i<max_n; i++){
p[i] = p[i-1] + f[i];
}
for(int i = 0; i< n; i++){
cout << p[a1[i]]- p[b1[i]] << endl;
}
}
int main() {
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
long long t;
t = 1;
// cin >> t;
while (t--) {
solve();
}
return 0;
}
Click to see test details