6847:Decision

题目描述
Notice:Don't output extra spaces at the end of one line.

Dodo and ddd rent a house together. The house has several bedrooms of different sizes. They all want to get the biggest one, so they come up with a strategy to allocate the biggest room. The strategy is as follows:

- Each of them chooses an integer in $[0,t]$ randomly, where $t$ is a constant value. Call the number chosen by them $v_1$ and $v_2$ respectively.

- Generate an array $\{X_n\}$: define $X_0=v_1+v_2$, for $n \geq 0$, define $X_{n+1}=(aX_n+c) \mod m$, where $a, c, m$ are constant values.

- If $X_{|v_1-v_2|}$ is an odd number, Dodo gets the biggest room. Otherwise, ddd gets it.

ddd wants to know the probability of him getting the biggest room. Please help him to calculate it. Please output the probability by using an irreducible fraction.
输入解释
The first line contains an integer $T(1 \leq T \leq 100)$, indicating the number of test cases.

Each test case contains one line, which contains $4$ integers $t, a, c, m(2 \leq m \leq 10^6, 0 \leq a, c < m, 0 \leq t < \frac{m}{2})$.

It is guaranteed that there are at most $12$ test cases with $m > 5000$.
输出解释
$T$ lines, each line contains an irreducible fraction, indicating the answer.
输入样例
5
7 1 0 29
7 0 1 29
77 77 77 777
84 74 26 363
10 15 76 9479
输出样例
1/2
1/8
84/169
3729/7225
71/121
来自杭电HDUOJ的附加信息
Recommend IceyWang

该题目是Virtual Judge题目,来自 杭电HDUOJ

源链接: HDU-6847

最后修改于 2020-10-25 23:34:53 UTC 由爬虫自动更新

共提交 0

通过率 --%
时间上限 内存上限
10000/10000MS(Java/Others) 524288/524288K(Java/Others)

·

·

·

·

登陆或注册以提交代码