import java.util.*; public class Auction {
static int m, k; static int earliest; static long n; static long lcm; static int[] firstMod, min, max, minMap, maxMap; public static class Tree { private class Entry { // if min or max is 0, then the subtree is empty int value; int min; int max; boolean exists; public Entry(int value) { this.value = value; } public String toString() { return value+"|m"+min+"|M"+max+"|"+(exists?"T":"F"); } } Entry[] tree; int size; boolean[] exist; public Tree(int max) { tree = new Entry[2 * max + 2]; exist = new boolean[max + 1]; size = 0; Entry emptyTree = new Entry(0); // dummy entry, used as empty subtree genTree(1, max, 1); for (int i = 0; i < tree.length; i++) { if (tree[i] == null) tree[i] = emptyTree; } } private void genTree(int L, int R, int at) { if (L > R) return; int M = (L + R) / 2; tree[at] = new Entry(M); genTree(L, M - 1, at * 2); genTree(M + 1, R, at * 2 + 1); } public void clear() { size = 0; clear(1); } public void clear(int at) { if (at >= tree.length || tree[at].min == 0) return; tree[at].min = 0; tree[at].max = 0; tree[at].exists = false; exist[tree[at].value] = false; clear(at * 2); clear(at * 2 + 1); } public boolean isEmpty() { return size == 0; } public int first() { return tree[1].min; } public int last() { return tree[1].max; } public void add(int n) { int at = 1; exist[n] = true; while (true) { if (n < tree[at].value) at *= 2; else if (n > tree[at].value) at = 2 * at + 1; else { if (!tree[at].exists) size++; tree[at].exists = true; break; } } updateMinMax(at); } public void remove(int n) { int at = 1; exist[n] = false; while (true) { if (n < tree[at].value) at *= 2; else if (n > tree[at].value) at = 2 * at + 1; else { if (tree[at].exists) size--; tree[at].exists = false; break; } } updateMinMax(at); } public boolean contains(int n) { return exist[n]; } private void updateMinMax(int at) { while (at >= 1) { Entry L = tree[0], R = tree[0], M = tree[at]; if (at * 2 < tree.length) L = tree[at * 2]; if (at * 2 + 1 < tree.length) R = tree[at * 2 + 1]; if (L.min != 0) M.min = L.min; else if (M.exists) M.min = M.value; else M.min = R.min; if (R.max != 0) M.max = R.max; else if (M.exists) M.max = M.value; else M.max = L.max; at /= 2; } } } public static class Sequence { int[] leading, repeat, first; long l, r, mod; public int get(int i) { if (i < l) return leading[(int) i]; i -= l; return repeat[(int) (i % r)]; } public String toString() { return Arrays.toString(leading)+"("+Arrays.toString(repeat)+")"; } public Sequence(int p1, long a, long b, long m) { mod = m; first = new int[(int) mod + 1]; int P = p1; List list = new ArrayList(); boolean[] seen = new boolean[(int) (m+1)]; for (int i = 1; i <= n; i++) { if (seen[P]) { int start = list.indexOf(P); leading = new int[start]; repeat = new int[list.size() - start]; for (int j = 0; j < start; j++) leading[j] = list.get(j); for (int j = start; j < list.size(); j++) { repeat[j - start] = list.get(j); first[list.get(j)] = j + 1; } break; } else { list.add(P); } seen[P] = true; P = (int) (((a * P + b) % m) + 1); if (i == n) { leading = new int[(int) n]; repeat = new int[0]; for (int j = 0; j < n; j++) { leading[j] = list.get(j); } } } l = leading.length; r = repeat.length; } } public static long gcd(long a, long b) { return b == 0 ? a : gcd(b, a%b); } public static long ceil(long a, long b) { // assumes a >= 0 return (a+b-1)/b; } public static long floor(long a, long b) { if (a < 0) return -ceil(-a, b); return a/b; } public static long timesSeen(int p, int w) { if (P.first[p] == 0 || W.first[w] == 0) return 1; int mod = (int) ((((W.first[w] - P.first[p]) % W.r) + W.r) % W.r); long firstSeen = P.r * firstMod[mod] + P.first[p]; long k = Math.min(floor(firstSeen - P.first[p], lcm), floor(firstSeen - W.first[w], lcm)); firstSeen -= k * lcm; return (n - firstSeen) / lcm + 1; } public static void generateMinMax() { boolean[] seen = new boolean[(int)W.r]; int[] seenWhen = new int[k+1]; minMap = new int[(int) P.r]; maxMap = new int[(int) P.r]; earliest = 1000000000; for (int i = 0; i < W.r; i++) { long first = 0; if (P.l + 1 - (W.l + i + 1) > 0) first = ceil(P.l + 1 - (W.l + i + 1), W.r); // get the first time we see it after the leading P terms seenWhen[i] = (int)(W.r * first + W.l + i + 1); earliest = Math.min(earliest, seenWhen[i]); } if (P.r == 0) return; Tree window = new Tree((int)(W.mod)); for (int start = 0; start < W.r; start++) { long endW = start, L = 0, R = 0; int smallest = earliest; if (seen[start]) continue; window.clear(); int atW = start; //while (smallest <= Math.max(P.l + P.r, W.l + W.r)) { // nope. while (smallest - earliest < P.r) { // nope. seen[atW] = true; int startElement = W.repeat[atW]; long last = seenWhen[atW] + (window.size - 1) * P.r; while (last + P.r <= n) { if (L > R) { R = L; endW = atW; } int next = W.repeat[(int) endW]; if (window.contains(next)) break; window.add(next); last += P.r; endW += P.r; endW %= W.r; R++; } int when = seenWhen[atW]; if (!window.isEmpty() && when - earliest < P.r) { minMap[when - earliest] = window.first(); maxMap[when - earliest] = window.last(); } window.remove(startElement); seenWhen[atW] += W.r; atW += P.r; atW %= W.r; L++; if (atW == start) { // we've looped, HOPE THIS WORKS RIGHT smallest += W.r; } } } firstMod = new int[(int)W.r]; for (int i = 0; i < W.r / gcd(P.r, W.r); i++) { firstMod[(int) (P.r * i % W.r)] = i; } } public static Sequence P, W; public static void main(String[] args) { Scanner in = new Scanner(System.in); int t = in.nextInt(); for (int ca = 1; ca <= t; ca++) { n = in.nextLong(); int p1 = in.nextInt(), w1 = in.nextInt(); m = in.nextInt(); k = in.nextInt(); int a = in.nextInt(), b = in.nextInt(), c = in.nextInt(), d = in.nextInt(); P = new Sequence(p1, a, b, m); W = new Sequence(w1, c, d, k); generateMinMax(); lcm = 0; if (W.r > 0 && P.r > 0) lcm = (W.r / gcd(W.r, P.r) * P.r); min = new int[m+1]; max = new int[m+1]; for (int i = 0; i <= m; i++) min[i] = k+1; // lower bound: 0, upper bound: k+1 for (int i = 0; i < P.l; i++) { min[P.get(i)] = W.get(i); max[P.get(i)] = W.get(i); } for (int i = (int)P.l; i < P.l + P.r; i++) { int j = i; while (j < W.l) { min[P.get(i)] = Math.min(min[P.get(i)], W.get(j)); max[P.get(i)] = Math.max(max[P.get(i)], W.get(j)); j += P.r; } if (j < n) { int id = j + 1 - earliest; if (minMap[id] > 0) min[P.get(i)] = Math.min(min[P.get(i)], minMap[id]); if (maxMap[id] > 0) max[P.get(i)] = Math.max(max[P.get(i)], maxMap[id]); } } long terrible = 0; int maxMaxs = 0; for (int i = m; i >= 1; i--) { if (max[i] > maxMaxs) {
// System.out.println(“Terrible: ”+i+“,”+max[i]+“ ct=”+timesSeen(i,max[i]));
terrible += timesSeen(i, max[i]); maxMaxs = max[i]; } } long bargains = 0; int minMins = k+1; for (int i = 1; i <= m; i++) { if (min[i] < minMins) { bargains += timesSeen(i, min[i]); minMins = min[i]; } } System.out.printf("Case #%d: %d %d%n", ca, terrible, bargains); } }
}
![[del.icio.us]](http://images.del.icio.us/static/img/delicious.small.gif){kind=small}
