Codeforces Round #305 Div2 C: Mike and Frog

問題

codeforces.com

解法

h[i]->a[i]になるまでの時間first[i]とa[i]->a[i]の時間cycle[i]を取っておく。求める時間secはsec=first[i]+cycle[i]*zのような形になるので、ゴリ押しでループさせていけば良い。（それでも間に合う）

sec < first[i]+cycle[0]*cycle[1]*2であることを利用する。

コード

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int m = sc.nextInt();
		long[] first = new long[2];
		long[] cycle = new long[2];
		for (int i = 0; i < 2; i++) {
			int h = sc.nextInt();
			int a = sc.nextInt();
			int x = sc.nextInt();
			int y = sc.nextInt();
			if (h != a) {
				first[i] = grow(h, a, x, y, m);
			}
			if (first[i] == -1) {
				System.out.println(-1);
				sc.close();
				return;
			}
			cycle[i] = grow(a, a, x, y, m);
		}
		sc.close();

		if (first[0] == first[1]) {
			System.out.println(first[0]);
			return;
		}
		long end = Math.max(first[0], first[1]) + cycle[0] * cycle[1];
		end *= 2;
		while (Math.min(first[0], first[1]) <= end) {
			if (first[0] == first[1]) {
				System.out.println(first[0]);
				return;
			} else if (first[0] > first[1]) {
				if (cycle[1] == -1) {
					System.out.println(-1);
					return;
				}
				first[1] += ((first[0] - first[1] + cycle[1] - 1) / cycle[1]) * cycle[1];
			} else {
				if (cycle[0] == -1) {
					System.out.println(-1);
					return;
				}
				first[0] += ((first[1] - first[0] + cycle[0] - 1) / cycle[0]) * cycle[0];
			}
		}
		System.out.println(-1);
		return;
	}

	private static int grow(long h, long a, long x, long y, long m) {
		for (int second = 1; second <= m + 1; second++) {
			h = (x * h + y) % m;
			if (h == a) {
				return second;
			}
		}
		return -1;
	}

}