Sample test(s)
input
54 21 10 12 3
output
3
input
10231 21 01 21 1
output
-1
快被这题坑死了，，大题思路：
找到第一次到达a1的步数记录为p1,找到从a1再一次到达a1的步数q1
同理记录p2、q2
之后找到一个最小的数 t = p1 + q1 * x = p2 + q2 * y
这里的t肯定是小于 max(p1,p2) + q1 * q2的
#include<cstring>#include<iostream>#include<algorithm>using namespace std;typedef long long LL;const int maxn = 1000005;bool vis[maxn];LL mod;LL x1,y1,h1,a1,p1,q1;LL x2,y2,h2,a2,p2,q2;void solve(LL h,LL a,LL x,LL y,LL &p,LL &q){memset(vis,0,sizeof(vis));LL now = h,cnt = 0;p = -1,q = -1;while(1){if(vis[now]) break;if(now == a) {p = cnt; break;}vis[now] = 1;now = (now * x + y) % mod;cnt ++;}now = a; cnt = 0;memset(vis,0,sizeof(vis));while(1){if(vis[now]){if(now == a) q = cnt;break;}vis[now] = 1;now = (x * now + y) % mod;cnt ++;}}int main(){cin >> mod;cin >> h1 >> a1 >> x1 >> y1;cin >> h2 >> a2 >> x2 >> y2;solve(h1,a1,x1,y1,p1,q1);solve(h2,a2,x2,y2,p2,q2);if(p1 == -1 || p2 == -1)cout << "-1" << endl;else if(q1 == -1 && q2 == -1){if(p1 == p2)cout << p1 << endl;elsecout << "-1" << endl;}else if(q1 == -1){if(p1 >= p2){LL e = p1 – p2;if(e % q2 == 0)cout << p1 << endl;elsecout << "-1" << endl;}elsecout << "-1" << endl;}else if(q2 == -1){if(p2 >= p1){LL e = p2 – p1;if(e % q1 == 0)cout << p2 << endl;elsecout << "-1" << endl;}elsecout << "-1" << endl;}else{LL max_v = max(p1,p2) + q2 * q1;LL ok = -1;for(LL i = p1; i <= max_v; i += q1){LL d = i – p2;if(d >= 0 && (d % q2 == 0)){ok = i;break;}}cout << ok << endl;}return 0;}
变幻原是永恒，我们唯有用永恒的诺言制约世事的变幻。
