U419131 Phi 的游戏

**时间限制：** 1.5 秒 **空间限制：** 512 MB **提交前的提示：** 如果想使用 `C++` 输出指定位数的小数，可以使用 `stdio.h` 库或者 `iostream` 以及 `iomanip` 库。例：将浮点数 $x$ 保留三位小数输出可以使用 `printf("%.3f", x)` 或者 `std::cout

Picar 和 Roman 是两个非常喜欢玩各种游戏的赌徒。这一天，他们又发现了一种新的数字游戏，名叫 $\varphi$ 的游戏 (Phi Games)。 $\varphi$ 的游戏是双人游戏，每局游戏由任意一个正整数 $N$ 开始，由两人轮流对当前的数字进行操作。轮到其中任意一方进行操作时，玩家可以有以下三种选择： 1. 大喊： " $\varphi : 1$ ! " 并将当前的数字 $n$ 变为 $\varphi(n)$; 2. 大喊： " $\varphi : 2$ ! " 并将当前的数字 $n$ 变为 $\varphi(2n)$; 3. 大喊： " $\varphi : K$ ! " 并将当前的数字 $n$ 变为 $\varphi(n-K)$，其中 $K$ 是一个双方在开始游戏之前约定好的非负整数。 其中 $\varphi(n)$ 表示的是在 $1$ 到 $n$ 这 $n$ 个正整数中，有多少个正整数与 $n$ 互质，如 $\varphi(1)=1,~\varphi(4)=2,~\varphi(10)=4$。根据这一定义可知，$\varphi(n)$ 的定义域是 $\mathbb{N}^+$，所以如果选择第 3 种操作 " $\varphi : K$ ! "，需要保证当前的数字 $n>K$。 两名玩家轮流操作，如果谁在进行操作之后得到了已经出现过的数字，谁就输掉了本局游戏。例如，玩家 A 对当前的数字 $1$ 选择了操作 1 " $\varphi : 1$ ! "，由于 $\varphi(1)=1$ 是出现过的数字，玩家 A 输掉本局游戏，对手获胜。 $\varphi$ 的游戏考验了玩家的心算能力和逻辑推理能力。可惜，由于 Picar 和 Roman 足够聪明，只要指定一个 $K$ 和最开始的数字 $N$，他们就可以算出是先手还是后手有必胜策略。如果对于某个确定的 $K$ ，以 $N$ 开始游戏时先手有必胜策略，则称这个 $N$ 为先手必胜态；否则后手有必胜策略，称 $N$ 为后手必胜态。为了使得这个游戏（对他们来说）更有趣，他们决定对游戏进行扩展： - 玩家先指定 $K$，并选择两个正整数 $L,R$，由系统在 $[L, R]$ 中的先手必胜态中随机挑选一个 $r$ 作为右端点； - 由后手选择一个正整数左端点 $l$，需要保证 $1\le l\le r$； - 开始一局游戏时，系统从 $[l,r]$ 中等概率地挑选一个正整数 $N$，作为游戏开始时先手操作的数字。 尽管 Picar 和 Roman 足够聪明，计算修改后的游戏对他们来说也需要花费不少的时间。于是，他们找到了你，想让你帮忙计算一下修改后的游戏平衡性。即：给定参数 $L,R,K$，求后手对于任意 $r$ 能**选出最优的 $l$ 使得后手胜率最大**时，先手的平均胜率。

从标准输入读入数据。 输入仅一行，包含三个非负整数 $L,R,K$，含义如题目描述所示。保证 $L\le R$，且在 $[L,R]$ 中至少存在一个先手必胜态。

输出到标准输出。 输出一个实数，表示在给定的参数 $L,R,K$ 下，修改后的游戏的先手平均胜率。 记答案为 $a$，而你的输出为 $b$，那么当且仅当 $|a-b|

### 样例 1 解释 此时 $2,4,5,7,9,10$ 为先手必胜态，$1,3,6,8$ 为后手必胜态。 - $r=2$ 对应的最优左端点 $l$ 为 $1$，此时先手胜率为 $1/2$； - $r=4$ 对应的最优左端点 $l$ 为 $3$，此时先手胜率为 $1/2$； - $r=5$ 对应的最优左端点 $l$ 为 $1$，此时先手胜率为 $3/5$； - $r=7$ 对应的最优左端点 $l$ 为 $6$，此时先手胜率为 $1/2$； - $r=9$ 对应的最优左端点 $l$ 为 $8$，此时先手胜率为 $1/2$； - $r=10$ 对应的最优左端点 $l$ 为 $6$，此时先手胜率为 $3/5$。 故先手的平均胜率为 $(1/2+1/2+3/5+1/2+1/2+3/5)/6=8/15\approx 0.5333$。 ### 子任务 对于所有的数据，保证 $1\le L\le R\le 10^7,~0\le K\le 10^7$，在 $[L,R]$ 中至少存在一个先手必胜态。 | 测试点编号 | $L,R\le$ | 特殊性质 | | :-----: | :----: | :-----: | | $1$ | $6$ | $K