Problem 1C. ぱぴぷぴぷぴぱ!

Problem 1C. ぱぴぷぴぷぴぱ!

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Problem 1C. ぱぴぷぴぷぴぱ!

时间限制:1s

空间限制:64MB

题目背景

Screenshot_20230911_183829_Phigros

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\)(即分子和分母互质)。

2023秋 悬赏令第一周

未参加
状态
已结束
规则
OI
题目
6
开始于
2023-10-01 18:30
结束于
2023-10-08 00:00
持续时间
149.5 小时
主持人
参赛人数
101