Problem 1C. ぱぴぷぴぷぴぱ!
该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
Problem 1C. ぱぴぷぴぷぴぱ!
时间限制:1s
空间限制:64MB
题目背景
pzr 喜欢玩音游,但是最近的新歌曲让他非常苦恼。
题目描述
新歌曲的难度系数为 \(N\),pzr 成功通关该首歌曲的概率 \(P\) 与他的游玩经验值 \(E\)、歌曲难度系数 \(N\) 满足以下关系:
\[P=\min(1.0,\frac{E}{N})\]
pzr 的初始经验值为 \(0\),每次游玩该歌曲 之后,他都能获取 \(1\) 经验,并且有一定概率(根据上述公式)通关该歌曲。
请问, pzr 首次通关该首歌曲所需的 期望游玩次数 是多少?
输入格式
仅一个整数 \(N\),表示歌曲的难度系数。
输出格式
可以证明,存在唯一的一组整数对 \((P, Q)\) 使得该期望可以表示为最简分数 \(\frac{P}{Q}\),其中 \(1\le P,Q\le 2^{30}-1\) 且 \(\gcd(P,Q)=1\)(即分子和分母互质)。
请依次输出满足条件的 \(P\) 和 \(Q\),用空格隔开。
样例输入1
2
样例输出1
5 2
样例1解释
第一次游玩, pzr 不可能通关该歌曲,但 pzr 的经验将增长 1。
第二次游玩, pzr 有 \(1/2\) 的概率通关该歌曲,如果没有通关, pzr 的经验将增长到 2。
如果 pzr 没有在第二次通关该歌曲,则必须游玩第三次,这一次 pzr 一定能通关该歌曲。
因此,有 1/2 的概率需要 2 次游玩,有 1/2 的概率需要 3 次游玩。
期望游玩次数是 \(1/2 * 2 + 1/2 * 3 = 5/2\)
样例输入 2
10
样例输出 2
7281587 1562500
数据范围及限制
对于 \(60\%\) 的数据,\(1\le n\le 3\)
对于 \(100\%\) 的数据,\(1\le n\le 10\)
保证存在唯一的一组整数对 \((P, Q)\) ,使得该期望可以表示为最简分数 \(\frac{P}{Q}\),其中 \(1\le P,Q\le 2^{30}-1\) 且 \(\gcd(P,Q)=1\)(即分子和分母互质)。