| D |
D. Soldier and Number Game
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
Two soldiers are playing a game. At the beginning first of them chooses a positive integer n
and gives it to the second soldier. Then the second one tries to make
maximum possible number of rounds. Each round consists of choosing a
positive integer x > 1, such that n is divisible by x and replacing n with n / x. When n becomes equal to 1
and there is no more possible valid moves the game is over and the
score of the second soldier is equal to the number of rounds he
performed.
To make the game more interesting, first soldier chooses n of form a! / b! for some positive integer a and b (a ≥ b). Here by k! we denote the factorial of k that is defined as a product of all positive integers not large than k. What is the maximum possible score of the second soldier?
Input
First line of input consists of single integer t (1 ≤ t ≤ 1 000 000) denoting number of games soldiers play.Then follow t lines, each contains pair of integers a and b (1 ≤ b ≤ a ≤ 5 000 000) defining the value of n for a game.
Output
For each game output a maximum score that the second soldier can get.
Examples
Input
2 3 1 6 3
Output
2 5 Idea : When you have more than 10^5 test cases and time in the range of 2-3 seconds You can be sure Either you have to answer in log(N) But when you have 10^6 test cases It's better to pre-calculate answers and save them and the complexity would be preprocessing+ testcase*O(1) .
a!/b! = a*(a-1)*(a-2)*.....(b+1)
|
#)Using sieve to calculate any prime factor of a range of numbers.
#)Calculating all prime factors of a range of numbers in O(N).
#)Storing sum of all prime factors of a range of numbers using prefix sum.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 | /**************************************** @_@ Cat Got Bored *_* #_# *****************************************/ #include <bits/stdc++.h> #define loop(i,s,e) for(int i = s;i<=e;i++) //including end point #define pb(a) push_back(a) #define sqr(x) ((x)*(x)) #define CIN ios_base::sync_with_stdio(0); cin.tie(0); #define ll long long #define ull unsigned long long #define SZ(a) int(a.size()) #define read() freopen("input.txt", "r", stdin) #define write() freopen("output.txt", "w", stdout) #define ms(a,b) memset(a, b, sizeof(a)) #define all(v) v.begin(), v.end() #define PI acos(-1.0) #define pf printf #define sfi(a) scanf("%d",&a); #define sfii(a,b) scanf("%d %d",&a,&b); #define sfl(a) scanf("%lld",&a); #define sfll(a,b) scanf("%lld %lld",&a,&b); #define mp make_pair #define paii pair<int, int> #define padd pair<dd, dd> #define pall pair<ll, ll> #define fs first #define sc second #define CASE(t) printf("Case %d: ",++t) // t initialized 0 #define INF 1000000000 //10e9 #define EPS 1e-9 using namespace std; int primefactor[5000010]; //Some prime factor int num_ofPF[5000010]; // Number of prime factors ll cum_sum_num_PF[5000010]; // Cumulative sum of number of PF s in a range bool visited[5000010]; void sieve(int N) { int SqN = (int)sqrt(N+1); ms(visited,false); for(int i = 2 ; i<=N; i++) //Need to go till n otherwise I can set the prime factors for numbers > SqN { if(visited[i]==false) for(int j = i; j <= N ; j+=i) { visited[j] = true; primefactor[j] = i; } } } void num_of_prime_factors(int N) { num_ofPF[1] = 0; for(int i = 2; i<=N; i++) { // cout<<i<<" last error"<<endl; //Debugging to find where I got the RTE num_ofPF[i] = num_ofPF[i / primefactor[i] ] + 1; } } void cum_sum_PF(int N) { cum_sum_num_PF[2] = num_ofPF[2]; for(int i = 3; i<=N; i++) { cum_sum_num_PF[i] = cum_sum_num_PF[i-1] + num_ofPF[i]; } } int main() { //pre processing sieve(5000004); num_of_prime_factors(5000004); cum_sum_PF(5000004); //cout<<primefactor[2237]<<endl; //cout<<2237*2237<<endl; int tc; sfi(tc); while(tc--) { int a , b; sfii(a,b); pf("%lld\n",cum_sum_num_PF[a] - cum_sum_num_PF[b]); //O(1) per test case } return 0; } |
