bzoj#P1583. [Usaco2009 Mar]Moon Mooing 哞哞叫

[Usaco2009 Mar]Moon Mooing 哞哞叫

题目描述

满月的时候,和狼一样,牛们也在月光下叫。他们从不嚎叫,而是哞叫。

每次哞叫都有一个时长,可能是 11 秒,也可能是 10910^9 秒或更久,牛们真的非常能叫。当然,没有牛哞叫时长会超过或等于 2632^63 秒。

牛们的哞叫可以找到规律,这并不奇怪。贝茜会选择一个整数 cc 来作为初始时长。之后,牛们根据两条公式确定更多的时长。这两条公式是:

f1(c)=a1cd1+b1f_1(c)=\frac{a_1\cdot c}{d_1}+b_1

f2(c)=a2cd2+b2f_2(c)=\frac{a_2\cdot c}{d_2}+b_2

公式中 a1,b1,d1,a2,b2,d2a_1,b_1,d_1,a_2,b_2,d_2 均为整数。牛们用这两条公式不断地迭代、计算,算得大量的时长。然后她们将这些时长排序,剔除重复的时长,最后取前 nn 个整数为她们 nn 次哞叫的时长。请你计算,第 nn 次哞叫的时长是多少。

输入格式

  • 11 行:两个整数:c,nc,n

  • 22 行:三个整数:a1,b1,d1a_1,b_1,d_1

  • 33 行:三个整数:a2,b2,d2a_2,b_2,d_2

输出格式

  • 11 行:一个整数,表示第 nn 次哞叫的时长。
3 10 
4 3 3 
17 8 2 
65 

数据规模与约定

对于 100%100\% 的数据,1c1001 \le c \le 1001<n<4×1061 < n < 4\times 10^61d1<a1201 \le d_1 < a_1 \le 201d2<a2201 \le d_2 < a_2 \le 200b1,b2200 \le b_1,b_2 \le 20

题目来源

Usaco2009 Mar Gold