[洛谷题解] CF547A Mike and Frog

叶ID

2019-10-23 14:48:27

Solution

题目链接:[CF547A Mike and Frog](https://www.luogu.org/problemnew/solution/CF547A) ### 题目大意 你有两个数 $H_1$、$H_2$。每次操作,你可以将 $H_1$ 变成 $(H_1 \cdot x_1 + y_1)\ mod\ M$,$H_2$ 变成 $(H_2 \cdot x_2 + y_2)\ mod\ M$ (两个变换会在一次操作时同时进行)。 问,你至少需要进行多少次操作,才能使得 $H_1 = A_1$ 和 $H_2 = A_2$ 同时满足。 数据范围:$H_1,x_1,y_1 <M$ ,$H_2,x_2,y_2 < M$ ,$2 \leq M \leq 10^6$ ### 解题思路 注意到本题 $M$ 只有 $10^6$,我么可以对于 $H_1$ 和 $H_2$ 分别暴力模拟。 对于一个数 $a$,如果不断进行操作,其变化规律应当如下: a → b → (c → d → e → f) → (c → d → e → f) → ... 感性理解一下,我们发现这个数进行一定次数操作后一定会进入一个循环。 我们称这个数达到第一个 $c$ (如上面的描述)之后就算进入了循环,到达第二个 $c$ 时算“发生循环”。那么,一个数的变化规律可以这么描述: - 对于任意一个数,其变换 $0$ 次或若干次就会进入一个长度大于 $0$ (废话),且小于等于 $M$ 的循环。 比如,上面的描述中,$a$ 在变换两次后就进入了一个长度为 $4$ 的循环。 我们用 $a^k$ 表示数 $a$ 操作 $k$ 次后的结果,用 $rd_a$ 表示 $a$ 进入循环前的变换次数,用 $r_a$ 表示 $a$ 进入的循环的长度。 对于 $H_1$,我们先暴力求出一个最小的 $cnt_{H_1}$(其实这样表示不准确,但是为了和$rd$、$r$的表达方式对等所以这么写),使得 $H_1^{cnt_{H_1}} = A_1$。我们还可以暴力求出 $rd_{H_1}$ 和 $r_{H_1}$。 然后我们很容易知道 $H_1^x = A_1$ 的条件。 - 如果 $cnt_{H_1} < rd_{H_1}$,则当且仅当正整数 $k$ 满足 $k = cnt_{H_1}$ 时,有 $H_1^k = A_1$ - 否则,当且仅当正整数 $k$ 同时满足以下条件时,有 $H_1^k = A_1$ - $k \geq rd_{H_1}$ (显然) - $(k - rd_{H_1})\ mod\ r_{H_1} = (cnt_{H_1} - rd_{H_1})$ (即,经过若干次循环以后会回到我们需要的位置) 然后我们对于 $H_2$ 也这样计算。随后我们分类讨论如何求得答案$ans$。 - 如果两个数的 $cnt$ 均小于 $rd$,那么,$ans$ 必须满足 $ans = cnt_{H_1}$ 和 $ans = cnt_{H_2}$。那么,当且仅当 $cnt_{H_1} = cnt_{H_2}$ 时有解,解是 $cnt_{H_1}$。 - 如果只有一个数的 $cnt$ 小于 $rd$,不妨令 $cnt_{H_1} < rd_{H_1}$。那么,必定有 $ans = cnt_{H_1}$。那么,当且仅当 $cnt_{H_1} \geq rd_{H_2}$ 且 $(cnt_{H_1} - rd_{H_2})\ mod\ r_{H_2} = (cnt_{H_2} - rd_{H_2})$ 时有解,解是 $cnt_{H_1}$。 - 如果没有一个数的 $cnt$ 小于 $rd$,那么,$ans$ 必须满足: - $ans \geq rd_{H_1}$ $\texttt{\color{grey}condition 1}$ - $ans \geq rd_{H_2}$ $\texttt{\color{grey}condition 2}$ - $(ans - rd_{H_1})\ mod\ r_{H_1} = (cnt_{H_1} - rd_{H_1})$ $\texttt{\color{grey}condition 3}$ - $(ans - rd_{H_2})\ mod\ r_{H_2} = (cnt_{H_2} - rd_{H_2})$ $\texttt{\color{grey}condition 4}$ 那么对于第三种情况,我们定义变量 $p$,并赋值为满足条件1和3的最小值。很显然,此时 $p = cnt_{H_1}$。 随后,我们不停地将 $p$ 的值增加 $r_{H_1}$ (可知这样不会破坏条件1和3),直到其满足条件2。由于 $rd_{H_2}$ 最大只能为 $M-1$,所以不会超时。此时的 $p$ 已经同时满足条件1,2和3。 最后我们再将 $p$ 的值不停增加 $r_{H_1}$ (可知这样不会破坏条件1,2,3),直到 $p$ 满足条件4(此时答案为 $p$),或者已经增加了超过 $M$ 次(此时无解)。 综合所有情况,就是正解了。 ### 代码 注意千万不要把 `y1` 定义成全局变量!如果评测机编译器版本较老,这会和 `math.h` 冲突,造成错误。 ```cpp // status: [Accepted] // oj: [%uContest] #include<bits/stdc++.h> using namespace std; // 不开 long long 见祖宗 typedef long long ll; #define int ll // 题目中的 M int mod1; // 让 h 每次以 h = (h * x + y) % mod1 的形式变换,返回变换到 a 所需的最少步骤数。 // 如果无法变换到 a,返回-1 // * flag: 是否允许在 h==a 时返回0 int findNext(int h,int a,int x,int y,bool flag = false) { int cnt = 0; if(flag && h==a) return 0; do { cnt++; h = (h * x + y) % mod1; // 如果变换超过 M 次还没有找到答案,那么此时肯定已经“发生循环”,不可能还会找到答案。 if(cnt > mod1) { return -1; } } while(h != a); return cnt; } int st[1000000]; int st_t = 0; // 让 h 每次以 h = (h * x + y) % mod1 的形式变换,返回 h 初次“进入循环”时变成的数。 int findCyclicNode(int h,int x,int y) { // 可以直接用数组统计是否出现。此处使用一个计数量(st_t),可以避免清空数组的麻烦 ++st_t; // 此处要先记录访问 h 一次,否则如果 h 本身就在循环内,会出现问题。 st[h] = st_t; // 由于一个数不断变换必定会出现循环,因此while(1)即可。 while(1) { h = (h * x + y) % mod1; // 第一个出现超过 1 次的值,一定是初次“进入循环”时的值 if(st[h] == st_t) return h; st[h] = st_t; } } // 除法上取整(避免double精度问题) // * 这份代码中没有用到此函数 int divCeil(int x,int y) { return x/y + int(bool(x%y)); } signed main() { #ifdef OFFLINE_JUDGE freopen("water.in","r",stdin); freopen("water.out","w",stdout); #endif // 不要将 y1 作为全局变量,否则要换个名字。 int h1,a1,x1,y1; int h2,a2,x2,y2; ios::sync_with_stdio(false); cin>>mod1>>h1>>a1>>x1>>y1>>h2>>a2>>x2>>y2; // 求cnt_{H_1} int cnt1 = findNext(h1,a1,x1,y1); int cnt2 = findNext(h2,a2,x2,y2); // H_1 和 H_2 有一个无法到达 A_1 或 A_2。无解。 if(cnt1 == -1 || cnt2 == -1) { cout<<-1<<endl; exit(0); } // 先寻找初次进入循环时到达的数字 int p1 = findCyclicNode(h1,x1,y1); int p2 = findCyclicNode(h2,x2,y2); // 再求循环长度 int r1 = findNext(p1,p1,x1,y1); int r2 = findNext(p2,p2,x2,y2); // 然后求初次进入循环之前的步骤数 int rd1 = findNext(h1,p1,x1,y1,true); int rd2 = findNext(h2,p2,x2,y2,true); // cnt - rd 在解法中被频繁使用,创建变量以图方便。 int d1 = cnt1 - rd1; int d2 = cnt2 - rd2; // 调试信息(在一般的平台下,使用cerr输出调试信息可避免一部分的“不删调试见祖宗”) cerr<<"1: "<<r1<<' '<<rd1<<' '<<d1<<endl; cerr<<"2: "<<r2<<' '<<rd2<<' '<<d2<<endl; // 如果两个数都有 cnt < rd (即 cnt - rd < 0) if(d1 < 0 && d2 < 0) { if(cnt1 == cnt2) { cout<<cnt1<<endl; } else { cout<<-1<<endl; } exit(0); } // 如果只有一个数 else if(d1 < 0) { if(cnt1 - rd2 >= 0 && (cnt1 - rd2) % r2 == d2) { cout<<cnt1<<endl; } else { cout<<-1<<endl; } exit(0); } else if(d2 < 0) { if(cnt2 - rd1 >= 0 && (cnt2 - rd1) % r1 == d1) { cout<<cnt2<<endl; } else { cout<<-1<<endl; } exit(0); } // 如果没有数满足 cnt < rd // 先使p满足条件1和3 int p = rd1 + d1; // 然后满足2 while(p < rd2) p += r1; // 最后满足4 for(int i=1;i<=r2+1;i++,p+=r1) { if((p-rd2) % r2 == d2) { cout<<p<<endl; exit(0); } } // 无解 cout<<-1<<endl; } ``` 评测记录:[R25577582](https://www.luogu.org/record/25577582)