2013年7月12日 星期五

11155 - Be Efficient


B
Next Generation Contest 3
Time Limit: 2 seconds
Be Efficient

一個整數序列有 N 個元素,其中
X0 = A
Xi = (( (Xi-1) * B + C ) % M)+1       for i = 1 to N-1
假設給定 A, B, C, M, N 的值。
在 X 序列中,找有多少連續子序列總合是 M 的倍數。

例如當  A = 2, B = 1, C = 2, M = 4, N = 4
=>
X0 = 2, X1 = 1, X2 = 4 and X3 = 3
連續子序列有 {2}, {2 1}, {2 1 4}, {2 1 4 3}, {1}, {1 4}, {1 4 3}, {4}, {4 3}, {3}. 
  
在這十個中,只有其中兩個 {1 4 3} 和 {4}是 4 個倍數。
 
Input
測資第一行會有一個整數 T (T < 500) 表示的測資組數。

對於每組測資會有 5 個整數 A, B, C, M, N。
(0 <= A, B, C <= 1000, 0 < M, N <= 10000)

Output
對於每組測資,輸出測資編號以及結果。 

Sample Input
Output for Sample Input
2
2 1 2 4 4
923 278 195 8685 793
Case 1: 2
Case 2: 34
 

Problem Setter: Mohiul Alam Prince
Moderator and Alternate Solution: Sohel Hafiz