RANDMOD - Random modulo n

no tags 

Kubík went to buy a pizza. To his surprise, the pizza box was made out of recycled… punch cards!

With his eagle eye, he deciphered the program the punch cards described:

n = read_input();
ans = 0;
while(n > 0)
    ans = ans + 1;
    n = random() % n;

random() is a function which returns uniformly random non-negative integers, and % is the modulus operator.

Now he wonders what the expected value of ans would be for a given initial value of n, and he is unable to enjoy his pizza until someone computes the answer for him.


The first line contains an integer 1 ≤ T ≤ 5 - the number of test cases.

Each of the next T lines contain a single integer n, where 1 ≤ n ≤ 300 000. The sum of n within an input file won't exceed 300000.


Output the expected value of the variable ans – that is, the sum of v × (probability that ans will end up with value v), for all possible values v.

Your answer will be considered correct if the absolute or relative error does not exceed 10−9. Make sure to print enough decimal places.






In the first case, either random()%2 = 0 with probability 1/2, which leads to ans = 1, or random()%2 = 1 with probability 1/2, after which we certainly get random()%1 = 0, so ans = 2. Expected value of ans is therefore 1 × 1/2 + 2 × 1/2 = 1.5.

hide comments
baraniec: 2019-08-02 11:26:19

It works fine now. AC finally. Very nice problem anyway!

hodobox: 2019-08-02 01:58:05

Unfortunately, a recent update in SPOJ's compiler killed my judge. I removed it from classical temporarily until I fixed the issue. It seems to now have been fixed - anyone affected please resubmit your solution to get a different result than Internal Error :).

For whatever strange reason, this movement of the problem deleted all the comments!? Sigh.

Last edit: 2019-08-02 01:58:32

Added by:Hodobox
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Resource:own problem