提示: 欢迎访问OurACM平台。
Problem 1927 取数游戏

Accept: 17    Submit: 58
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

AC是一个聪明的小孩,经常玩一些益智游戏。但他并不满足于玩别人发明的游戏,他也想着创造一些新的游戏玩法。

某日,AC灵机一动,又想到了一个数学游戏并且编程写了出来给实验室的队友们玩。首先玩家选择一个整数M,接着系统随机排列0到M-1之间的不重复的M个数。例如玩家如果选择7,那么系统就会生成{0,6,5,1,3,4,2} ,{0,1,2,3,4,5,6}…这样合法的序列,不会生成{0,0,1,2,3,4,5} ,{0,1,2,3,4,7,5} …这样不合法的序列。假设这M个不重复的数保存在A数组中,接着系统给出一个大小也为M的B数组,以及一个非负整数D。

游戏开始后,每一轮玩家只能执行下面的其中一种操作:

1. 从A数组中取出一个数(A[i]),并且在取出的位置填入-1,如果玩家原来手上已经取了一个数了,那么则用新取的数替换掉原来的数,并且玩家需要付出B[i]的“LB”(LB是游戏系统中的一种虚拟货币的单位)。

2. 如果玩家手上现在的数的大小为游戏开始时候的A[i](这里为了方便描述于是用A[i]表示手上的值以及它原先在A[]中的位置i,实际上此时A数组中A[i] = -1),则对于现存的任意的A[j](必须非负),如果满足j > i并且A[j] = A[i] * D^k(mod M)(k是一个非负整数),那么玩家就可以放弃A[i],选择A[j],并且在j的位置填入-1。此时玩家需要付出(k + A[j] * k)的”LB”,其中k是满足A[j] = A[i] * D^k(mod M)的最小非负整数。

注意:每轮结束,玩家手上只能有一个数。这也意味着第一轮玩家只能进行第一种操作。

现在游戏的目标是让A数组中的M个数都为-1。并且最终所花费的”LB”要最少,通过这个游戏的人都将获得AC的签名照一张。为了得到这个奖品,队员们都在绞尽脑汁想办法编程解决这个问题。

Input

首先第一行为T,表示有T组数据。接下来为每组数据的结构:

每组数据,第一行有两个整数M,D.(1 <= M <= 100, 0 <= D <= 10^9)

接着一行有M个数,表示合法的A数组中的M个数。

再接下来一行有M个数,表示B数组中的M个数,其中(0 <= B[i] <= 100, 0 <= i < M)。

Output

对于每组数据输出一行先输出组数(从1开始),接着输出通过游戏所需要的最少的”LB”。

Sample Input

2 3 2 0 2 1 10 20 30 3 3 1 2 0 1 5 3

Sample Output

Case 1: 32 Case 2: 7

Hint

样例1中 1. 玩家选择0,付出10 ”LB”。 2. 玩家选择2抛弃0,付出20 ”LB”。 3. 因为1 = 2 * 2^1 (mod 3),因此玩家抛弃2选择1,付出(1 + 1 * 1) = 2的”LB”。 因此答案为10 + 20 + 2 = 32 的”LB” 样例2中 1. 玩家选择1,付出1 ”LB”. 2. 因为1 * 3^1 = 0 (mod 3), 所以玩家抛弃1选择0,付出(1 + 1 * 0) = 1的”LB” 3. 玩家选择2抛弃0,付出5 “LB” 因此答案为1 + 1 + 5 = 7 “LB”

Source

FOJ有奖月赛-2010年06月

Submit  Back  Status  Discuss