### singh1495's blog

By singh1495, history, 5 years ago,

problem //////////////////////////////////////////////////// Expected Xor

Given a random variable X , and another integer N, this random variable X can take any value between 1 and N

with equal probability.

Now, we define a function F(X)

:

F(X)
The bitwise exclusive OR of all the digits of X. For example, for X=34536,F(X)=3⊕4⊕5⊕3⊕6=7

.

Considering X can take any value between 1 and N with equal probability, you are to find expected value of F(X)

. Can you do it ?

The answer equals to P/Q where P/Q is an irreducible fraction, i.e, P and Q

are co-prime to each other.

You can read more about expected value of a random variable here.

Input:

The first line of the input contains T

, denoting the number of test cases.

The next T lines contain a single positive integer N

.

Output:

For each test-case, print the answer in a separate line in the form of P/Q where P/Q is an irreducible fraction i.e. P and Q

are co-prime to each other.

Constraints:

1≤T≤105

1≤N≤1018

4 1 3 5 10

1/1 2/1 3/1 23/5

Explanation

For N=1 , there is only one possible value X can take which is 1. Hence expected value of X=1

.

For N=3 , there are three possible values of X ,i.e, 1,2 and 3. Hence, expected value of X=1/3∗1+1/3∗2+1/3∗3=2

.

For N=10 , X can take all the values from 1 to 9 where X will be equal to 1 for both 1 and 10. Hence, X=2/10∗1+1/10∗(2+3+4+5+6+7+8+9)=23/5

. my code

http://ideone.com/SRbjnv

please anyone great guy tell me where this code is going on wrong thanx in advance And explain how I can solve this

• -11

 » 5 years ago, # |   0 Auto comment: topic has been updated by singh1495 (previous revision, new revision, compare).
•  » » 5 years ago, # ^ |   0 return (!b ? a : gcd(b, a%b);