1836: Nestable

We make cardboard boxes. We manufacture a variety of sizes and are concerned that storing them and transporting them will be a problem unless we can nest them into a reasonable number of nested stacks. Each box is a rectangular solid and thus has three side lengths. We say that Box A can be nested in Box B if its smallest length is strictly less than B‘s smallest length, its 2nd smallest length is strictly less than B‘s 2nd smallest length, and its largest length is strictly less than B‘s largest length. No diagonal nesting is allowed. We have automated the manufacturing process so that random sized boxes are produced. We specify values a, p, and n and the machine produces n boxes with dimensions: (a,a^2,a^3) (a^4,a^5,a^6) (a^7,a^8,a^9) ... (a^(3n-2),a^(3n-1),a^(3n)) where a^j denotes (a to the jth power) mod p. Given the positive integer values a, p, and n,please return the size of the largest nestable collection of boxes, where a collection is nestable if every pair of boxes from the collection can be nested. The sequence of boxes can be generated by int length=1; for(int i=0; i<n; i++) { length = (length*a)%p; int x=length; length = (length*a)%p; int y=length; length = (length*a)%p; int z=length; //process this box, which has dimensions x,y,z }

Each case contains three number a, p, n. p is between 2 and 2,000,000,000 inclusive a is between 1 and p-1 inclusive no power of a is divisible by p a*p is less than or equal to 2,000,000,000 n is between 1 and 50,000 inclusive

output the size of the largest nestable collection of boxes.

10 15 3
10 17 4
10 100000007 40000
93 21505374 40000
7 22 8 

1
2
1299
151
3

for the first case,The random generator produces 10, (10*10)%15=10, 10*10%15=10, ... so the three boxes are (10,10,10) (10,10,10) (10,10,10). No pair of boxes is nestable, so the largest nestable collection has size 1.