TopCoder problem "ModuleSequence" used in SRM 497 (Division I Level Three)



Problem Statement

    

You are given four longs K, N, A and B. Generate an integer list X of length B-A+1 using the following recursive definition: 

        X[0]=(K*A) MOD N
	(note that K*A may overflow a 64-bit integer variable)

        X[i]=(X[i-1]+K) MOD N

Given another two longs lower and upper, return the number of elements in the list which are between lower and upper, inclusive.

 

Definition

    
Class:ModuleSequence
Method:countElements
Parameters:long, long, long, long, long, long
Returns:long
Method signature:long countElements(long K, long N, long A, long B, long lower, long upper)
(be sure your method is public)
    
 

Constraints

-K will be between 0 and 10,000,000,000, inclusive.
-N will be between 1 and 10,000,000,000, inclusive.
-A will be between 0 and 10,000,000,000, inclusive.
-B will be between A and 10,000,000,000, inclusive.
-lower will be between 0 and N-1, inclusive.
-upper will be between lower and N-1, inclusive.
 

Examples

0)
    
2
7
1
5
2
5
Returns: 3
The generated list is: 2, 4, 6, 1, 3.
1)
    
9
1
0
7
0
0
Returns: 8
2)
    
20
12
21
30
1
11
Returns: 6
Note that K, A and B may be greater than N.
3)
    
30
89
112
200
80
88
Returns: 9
4)
    
890
1000
1000
10000
456
980
Returns: 4770

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=8741

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=14426&pm=8741

Writer:

stone

Testers:

PabloGilberto , Yarin , ivan_metelsky , Chmel_Tolstiy

Problem categories:

Brute Force, Math