题目大意
G准备玩
n
n
n场游戏,它心中有个胜率
x
=
a
b
x = \frac{a}{b}
x=ba,如果当前赢的局数 / 总局书 小于等于
x
x
x,那么他就会赢,否则它就会输。
给定
a
,
b
,
n
a,b,n
a,b,n,求他能赢多少局。
思路
图中画出了胜场比变化图。
如果当前胜场比
s
>
x
s > x
s>x,那么我们就会输,反之我们就会赢!
进行第
n
n
n局时,假如我们知道了此时的
s
s
s,那么我们就能得本局是否会赢。
那么如何寻找
s
n
−
1
s_{n-1}
sn−1呢?我们可以发现,它一定在
x
x
x的两侧。比如
x
=
2.7
4
x = \frac{2.7}{4}
x=42.7,那么
s
n
−
1
s_{n-1}
sn−1要么是
2
4
\frac{2}{4}
42,要么是
3
4
\frac{3}{4}
43
- 假如
s
n
−
1
=
2
4
s_{n-1} = \frac{2}{4}
s
≤
x
s \le x
n
n
a
n
s
=
3
5
ans = \frac{3}{5}
- 假如
s
n
−
1
=
3
4
s_{n-1} = \frac{3}{4}
s
>
x
s > x
n
n
a
n
s
=
3
5
ans = \frac{3}{5}
可以发现,第
n
n
n局的答案和
s
n
−
1
s_{n-1}
sn−1无关,它是个”定值”,准确的来说:
a
n
s
=
⌊
(
n
−
1
)
∗
x
⌋
+
1
ans = \lfloor(n-1) * x \rfloor + 1
ans=⌊(n−1)∗x⌋+1,这个式子表示我们假设第
n
−
1
n-1
n−1局输掉了比赛,那么我们第
n
n
n局就会赢回来一局。
#include <cstdio>
#include <iostream>
using namespace std;
int main()
{
int T;
long long a, b, n;
scanf("%d", &T);
while(T--) {
scanf("%lld%lld%lld", &n, &a, &b);
printf("%lld\n",(n - 1) * a / b + 1);
}
return 0;
}