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
Sample Input (Plaintext Link)
4 1 3 5 10
Sample Output (Plaintext Link)
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
please anyone great guy tell me where this code is going on wrong thanx in advance
