古怪的钟 ## 来源 ZOJ Monthly, December 2002 (ZOJ1476) ## 题目描述 有一只很古怪的钟，它只有分针，刻度从0到59。只有到往它的盒子里投一些特制的硬币后，它的分针才会走动。你可以选择不同的硬币。然而一旦你选择某一种硬币后，就不能用其他硬币了。每种硬币有无限多枚。每种硬币都对应到一个数目d(1≤d≤1000)，表示当你投下这种硬币后，时钟的分针将从当前时间开始顺时针走当前时间的d倍刻度。例如，如果当前时间是45，d = 2，则分针顺时针走90分钟，然后分针指向的刻度是15。 给定初始时间s，1≤s≤59，以及硬币的类型d，编写程序求至少需要投多少枚这样的硬币才能使得分针指回到0刻度。 ## 输入描述 输入文件包含多个测试数据，每个测试数据占一行，为两个正整数s和d。输入文件的最后一行为两个0，代表输入结束。 ## 输出描述 对每个测试数据，输出最少的硬币数目。如不能使得分针指回0刻度，输出"Impossible"。 ## 样例输入 ```txt 59 59 59 58 0 0 ``` ## 样例输出 ```txt 1 Impossible ``` ## 提示 可以定义状态数组state[60]，state[i]=1表示投若干枚给定的硬币后可以到达时刻i；初始时，state[i]为0。对给定的s和d，模拟投第1枚硬币、第2枚硬币，…；如果在投币过程中，重复到达了某一时刻，说明存在一个环，后面到达的时刻又会是以前到达过的时刻，则输出Impossible。当到达时刻0时，设置state[0]的值为1，并输出当前所投的硬币数。