parameters X, A, B, M, p, q . In the next K lines are given integer numbers aa[i], bb[i], cc[i], dd[i] . The following code is used for generating the next random number using linear congruential generator with the starting value X and parameters A, B and modulo M : long long prior = X; long long next() { prior = (A * prior + B) % M; return prior; } The following code is used for extending the auxiliary sequences aa, bb, cc and dd : for (int i = K; i < N; i++) { aa [i] = aa [i - K] + next() % (2 * p) - p; bb [i] = aa [i] + 1 + next() % (2 * (bb [i % K] - aa [i % K])); cc [i] = cc [i - K] + next() % (2 * q) - q; dd [i] = cc [i] + 1 + next() % (2 * (dd [i % K] - cc [i % K])); } The final coordinates of the trapezoids are given by: for (int i = 0; i < N; i++) { a [i] = aa [i] * 1000000 + i; b [i] = bb [i] * 1000000 + i; c [i] = cc [i] * 1000000 + i; d [i] = dd [i] * 1000000 + i; } Note that above code generates trapezoids that satisfy all conditions of the problem, and '%' denotes the remainder of division .<br><br> Output For each of the test cases numbered in order from 1 to T , output "Case #i: " followed by a single integer, the minimum number of trapezoids that need to be removed such that the remaining trapezoids form a disconnected set. Constraints 1 d T d 20 1 d N d 300 000 1 d K d N 0 d X, A, B d 2 000 000 000 -2 000 000 000 d aa [i], bb [i], cc [i], dd [i] d 2 000 000 000 1 d p, q, M d 2 000 000 000 Examples In the first example, one can remove trapezoids 5 and 6 leaving two disconnected sets with trapezoids (1, 2, 3, 4) and (7, 8). In the second example, the coordinates of ten trapezoids are 1000000 4000000 3000000 5000000 7000001 8000001 2000001 6000001 2000002 7000002 2000002 5000002 5000003 7000003 2000003 6000003 4 6000004 2000004 3000004 4000005 5000005 3000005 8000005 -999994 6 6 2000006 4000007 6000007 1000007 7000007 -999992 8 -999992 2000008 5000009 6000009 9 7000009 Example input 5 8 8 1 1 1 1 1 1 1 3 1 3 2 5 6 10 4 8 5 8 6 9 2 4 7 11 11 13 10 13 7 9 12 16 14 15 14 15 12 16 10 2 2 1 1 7 2 2 1 4 3 5 7 8 2 6 100000 2 1 1 1 2 1 1 -2 -1 -1000001 -1000000 -1000001 -1000000 -2 -1 200 3 5 1 2 1117 11 13 1 10 1 10 2 11 2 11 3 12 3 12 10000 1 0 0 1 2 1 1 1 10000 1 100000 Example output Case #1: 2 Case #2: 6 Case #3: 50002 Case #4: 61 Case #5: -1 Divisor Function Optimization Let d(N) be the number of positive divisors of positive integer N .<br><br> Consider the infinite sequence x(n) = d(n) a / n b , n = 1, 2, 3, & where a and b are fixed positive integers. It can be shown that this sequence tends to zero. Hence it attains its maximum.<br><br> Denote it by p/q where p and q are co-prime positive integers. Your task is for given a and b find p and q modulo M = 10 9 +7 . But to keep input and output small you will be given tuples (b1; b2; a1; a2; c) and need to calculate the sum of (p mod M) for all pairs (a; b) such that b1 d b d b2 , a1 d a d a2 and a d c*b , and the same sum for q -values.<br><br> Input The first line contains a positive integer T , the number of test cases. T test cases follow. The only line of each test case contains five space separated positive integers b1, b2, a1, a2 and c .<br><br> Output For each of the test cases numbered in order from 1 to T , output "Case #i: " followed by a space separated pair of integers: the sum of (p mod M) for all pairs (a; b) mentioned above and the sum of (q mod M) for all such pairs. Note that you need to find the sum of residues not the residue of sum (see testcase 3 as a reference). Constraints 1 d T d 20 1 d b1 d b2 d 10000 1 d a1 d a2 d 250000 1 d c d 25 in each testcase the total number of pairs (a; b) for which the answer should be calculated does not exceed 100000 Example input 5 1 1 1 3 10 1 2 1 88 3 1 10 1 50 5 1 1 1 15 15 30 33 1 29 25 Example output Case #1: 1540 37 Case #2: 2377233 1491 Case #3: 75232917907 54682660016 Case #4: 5956707232 7441063226 Case #5: 116 116 Unfriending It's time to clean up your friends list after friending too many people on Facebook over the winter.<br><br> The set of your friends' u ser ids is F = { x 0 , x 1 , ..., x n-1 }. Each friend from F is on zero or more friend lists that you use to organize your friends. There are M friend lists, c 0 , c 1 , ..., c m- 1 .<br><br> You can unfriend (remove from F ) some of your friends, but because you want to stay in touch with people, you can only unfriend one person from each friend list. You may also choose not to unfriend anyone from friend list. Any friend that isn't on a friend li st cannot be unfriended.<br><br> Your goal is to find the maximum possible distance between the two friends whose user ids are the closest after you are done un friending people. The distance between user id x and user id y is defined as abs( x - y ). Input The first line contains a positive integer T , the number of test cases.<br><br> T test cases follow. The first line of each test case contains the number of friends N , and number of friend lists M , separated by a space. The second line contains x 0 and integer parameters a , b , and p , separated by spaces.<br><br> You must use these to generate the remaining numbers x 1 , &, x n- 1 according to this formula: x i = ( x i-1 * a + b ) mod p The next M lines of each test case define the friend lists for that test case. Each line consists of the following integers, se parated by spaces: size , y 0 , a , b . The size is the number of friends in the friend list.<br><br> y 0 is the index in F of the first friend in the list. You must generate the remaining friends in the friend list y 1 , &, y n-1 according to the following formula: y i = ( y i-1 * a + b ) mod n If a friend list contains more than one of a given index, consider it to only contain that index once. Constraints 1 d T d 20 2 d n d 50 000 0 d m d 1 500 0 d sum of sizes of all friend lists d 1 000 000 Numbers used in generators: 0 < a , p < 2 30 0 d b < 2 30 Output For each of the test cases numbered in order from 1 to T , output "Case #", followed by the case number, followed by ": ", followed by the maximum possible distance between the two closest user ids that you are still friends with for that case.<br><br> Example input 5 9 2 48071530 715583197 479567108 1050406 2 6 743132951 85415827 2 3 376850600 968665455 11 3 787260730 352556659 382266931 1057730 2 9 734333632 693274928 4 2 109921566 4305285 2 6 677574083 984173544 10 3 395307869 893188066 853669149 1056195 4 7 225271526 816658669 4 0 131869161 339696459 4 7 709635520 662395613 12 3 796525811 590453825 261103276 1050505 3 9 594759110 714784928 3 5 431449006 621243801 3 10 638845242 279357772 12 2 609821186 802201942 33450613 1048819 4 3 988115593 116841583 4 0 327812052 590896542 Example output Case #1: 7392 Case #2: 5130 Case #3: 15318 Case #4: 63175 Case #5: 5814

less