
ZOJ Problem Set  3265
There is a strange game played on a special machine. The game has m prizes labeled from 0 to m1. First, you are given n tickets, on which there is a number a_{i}. For each time, you can put one ticket into the machine. By pressing the button on the machine you will get a number. You can press the button as many times as you like, but at least once. If you press k times, the number from the machine will be a_{i}^{k} mod m, namely b_{i}, and then you can take away the prize labeled b_{i} as your trophy. Note that one ticket can only be used once, and same b_{i} refers to same prize, which you can only take once. Given n, m and a_{i}, you need to find the maximum number of different prizes you can get. Input The input contains no more than 30 cases. Each case has 2 lines. The first is two integers n, m (0 ≤ n ≤ 200, 0 < m ≤ 10^{9}). The second line contains n integers a_{0}, a_{1}, ..., a_{n1} (0 ≤ a_{i} ≤ 10^{9}). Proceed to the end of file. Output For each case output a integer, indicating the maximum number of different prizes you can get. Sample Input 2 2 1 2 Sample Output 2 Author: LI, Cheng Source: ZOJ Monthly, November 2009 