此题主要学到了处理循环节的问题。
对于每个生物而言,有可能有无数能到a1,有可能仅1次到a1,也可能一次也到不了a1
对于一次也到不了,直接输出-1
对于仅1次跑到a1,for m次,如果没有就没有了
对于无数次,联立同余方程,可以用EXGCD或者EXCRT求解。
#pragma warning(disable:4996) #include<iostream> #include<algorithm> #include<bitset> #include<tuple> #include<unordered_map> #include<fstream> #include<iomanip> #include<string> #include<cmath> #include<cstring> #include<vector> #include<map> #include<set> #include<list> #include<queue> #include<stack> #include<sstream> #include<cstdio> #include<ctime> #include<cstdlib> #define INF 0x3f3f3f3f #define inf 0x7FFFFFFF #define MOD 1000000007 #define moD 1000000003 #define pii pair<int,string> #define eps 1e-8 #define equals(a,b) (fabs(a-b)<eps) #define bug puts("bug") #define re register #define fi first #define se second const int maxn = 1e6 + 5; const double Inf = 10000.0; const double PI = acos(-1.0); typedef long long ll; typedef unsigned long long ull; using namespace std; int f1, f2; int n; vector<ll> v1, v2; ll ai[maxn], bi[maxn]; ll mul(ll a, ll b, ll mod) { ll res = 0; while (b > 0) { if (b & 1) res = (res + a) % mod; a = (a + a) % mod; b >>= 1; } return res; } ll exgcd(ll a, ll b, ll& x, ll& y) { if (b == 0) { x = 1; y = 0; return a; } ll gcd = exgcd(b, a % b, x, y); ll tp = x; x = y; y = tp - a / b * y; return gcd; } ll excrt() { ll x, y, k; ll M = bi[1], ans = ai[1]; for (int i = 2; i <= n; i++) { ll a = M, b = bi[i], c = (ai[i] - ans % b + b) % b; ll gcd = exgcd(a, b, x, y), bg = b / gcd; if (c % gcd != 0) return -1; x = mul(x, c / gcd, bg); ans += x * M; M *= bg; ans = (ans % M + M) % M; } return (ans % M + M) % M; } int main() { ll m, h1, a1, h2, a2, x1, y1, x2, y2; int pos1, pos2; scanf("%lld", &m); ll tmp, s1, s2, p1, p2; scanf("%lld %lld %lld %lld %lld %lld %lld %lld", &h1, &a1, &x1, &y1, &h2, &a2, &x2, &y2); tmp = h1; v1.push_back(tmp); for (int i = 1; i < 2 * m; i++) { tmp = (x1 * tmp + y1) % m; v1.push_back(tmp); } for (int i = 0; i < 2 * m; i++) { if (v1[i] == a1) { f1++; if (f1 == 1) s1 = i; if (f1 == 2) { p1 = i - s1; break; } } } if (f1 != 2) p1 = 0; tmp = h2; v2.push_back(tmp); for (int i = 1; i < 2 * m; i++) { tmp = (x2 * tmp + y2) % m; v2.push_back(tmp); } for (int i = 0; i < 2 * m; i++) { if (v2[i] == a2) { f2++; if (f2 == 1) s2 = i; if (f2 == 2) { p2 = i - s2; break; } } } if (f2 != 2) p2 = 0; if (!p2 || !p2) { for (int i = 0; i < m; i++) { if (v1[i] == a1 && v2[i] == a2) { printf("%d", i); return 0; } } puts("-1"); return 0; } if (!f1 || !f2) { puts("-1"); return 0; } for (int i = 0; i < m; i++) { if (v1[i] == a1 && v2[i] == a2) { printf("%d", i); return 0; } } n = 2; bi[1] = p1 , bi[2] = p2; ai[1] = s1 , ai[2] = s2; ll res = excrt(); if (res == -1) puts("-1"); else printf("%lld", res); }