Connection Status:
Competition Arena > ModuleSequence

ModuleSequence

SRM 497 · 2010-11-01 · by stone

SRM 497 · 2010-11-01 · by stone · Brute Force, Math
Class Name: ModuleSequence
Return Type: long
Method Name: countElements
Arg Types: (long long, long long, long long, long long, long long, long long)
Problem Statement

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.

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)
6
4
0
6
1
3
Returns: 3
1)
2
7
1
5
2
5
Returns: 3

The generated list is: 2, 4, 6, 1, 3.

2)
9
1
0
7
0
0
Returns: 8
3)
36
73
1
69
28
34
Returns: 7
4)
30
83
2
24
57
60
Returns: 2
28)
20
12
21
30
1
11
Returns: 6

Note that K, A and B may be greater than N.

129)
9214971511
9875961727
1000000000
9000000000
2500000000
7500000000
Returns: 4050238448

anti Yarin's approach (almost no benefit)

Submissions are judged against all 136 archived test cases, of which 7 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class ModuleSequence with a public method long long countElements(long long K, long long N, long long A, long long B, long long lower, long long upper) · 136 test cases · 2 s / 256 MB per case

Submitting as anonymous