You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

时间限制： 1.5 秒

空间限制： 512 MB

题目描述

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|<10^{-6}$ 时我们认为你的输出是正确的。

1 10 3

0.533333333333333333

样例 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$。

2021 5000 0

0.391970630667343944

214 7483648 57721

0.490802831707061571

子任务

对于所有的数据，保证 $1\le L\le R\le 10^7,~0\le K\le 10^7$，在 $[L,R]$ 中至少存在一个先手必胜态。