Sunday, April 10, 2016

VK Cup Prep Series 4

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;
}

No comments:

Post a Comment