Codeforces Round #305 (Div. 二) C. Mike and Frog

Codeforces Round #305 (Div. 2) C. Mike and Frog
链接 ：

http://codeforces.com/contest/548/problem/C

首先分别找出两个序列的循环节 和 循环节的起始位置，如果找到了循环节 终点却没有出现，那么进入循环节终点再也不能出现了。

如果在循环节内 我的做法就是算m次之后的每个值，在循环节之前就只有一个值。

#include <iostream>
#include <sstream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <stack>
#include <cmath>
#include <queue>
#include <map>
#include <set>
#define lson o<<1,l,m
#define rson o<<1|1,m+1,r
#define mem(a) memset(a,0,sizeof(a))
typedef long long ll;
const int N = 2000005;
const int M = 10005;
const ll mod = 1000000007;
const double PI = acos(-1.0);
const double eps = 1e-10;
using namespace std;


int f[N], s[N], st;
ll m;

ll cal(int* f, ll x, ll y, ll h) {
	int id = 0;
	while(1) {
		f[h] = id++;
		h = (h * x + y) %m;
		if(f[h]) {
			st = f[h];
			break;
		}
	}
	return id - st;
}

vector <ll> solve(ll a, ll cl, ll tmp) {
	vector <ll> t;
	if(a < tmp) t.push_back(a);
	else {
		for(int i = 0; i <= m; i++) {
			ll x = a + i * cl;
			t.push_back(x);
		}
	}
	return t;
}

int main() {
	ll h1, a1, x1, y1, h2, a2, x2, y2;
	cin >> m;
	cin >> h1 >> a1;
	cin >> x1 >> y1;
	cin >> h2 >> a2;
	cin >> x2 >> y2;
	
	ll clf = cal(f, x1, y1, h1);
	int st1 = st;
	ll cls = cal(s, x2, y2, h2);
	int st2 = st;
	
	if(f[a1] == 0 || s[a2] == 0) {
		cout << -1 << endl;
		return 0;
	}
	
	vector<ll> t1 = solve(f[a1], clf, st1);
	vector<ll> t2 = solve(s[a2], cls, st2);
	
	int l = 0, r = 0;
	while(l < t1.size() && r < t2.size()) {
		if(t1[l] > t2[r]) {
			r++;
			continue;
		}
		if(t1[l] < t2[r]) {
			l++;
			continue;
		}
		cout << t1[l] << endl;
		return 0;
	}
	
	cout << -1 << endl;
	return 0;
}