[洛谷题解] CF547A Mike and Frog
一道较为暴力的数学问题。思路简单,但是有助于增强代码能力。
题目大意#
你有两个数 、。每次操作,你可以将 变成 , 变成 (两个变换会在一次操作时同时进行)。
问,你至少需要进行多少次操作,才能使得 和 同时满足。
数据范围: , ,
解题思路#
注意到本题 只有 ,我么可以对于 和 分别暴力模拟。
对于一个数 ,如果不断进行操作,其变化规律应当如下:
a → b → (c → d → e → f) → (c → d → e → f) → …
感性理解一下,我们发现这个数进行一定次数操作后一定会进入一个循环。
我们称这个数达到第一个 (如上面的描述)之后就算进入了循环,到达第二个 时算“发生循环”。那么,一个数的变化规律可以这么描述:
- 对于任意一个数,其变换 次或若干次就会进入一个长度大于 (废话),且小于等于 的循环。
比如,上面的描述中, 在变换两次后就进入了一个长度为 的循环。
我们用 表示数 操作 次后的结果,用 表示 进入循环前的变换次数,用 表示 进入的循环的长度。
对于 ,我们先暴力求出一个最小的 (其实这样表示不准确,但是为了和、的表达方式对等所以这么写),使得 。我们还可以暴力求出 和 。
然后我们很容易知道 的条件。
- 如果 ,则当且仅当正整数 满足 时,有
- 否则,当且仅当正整数 同时满足以下条件时,有
- (显然)
- (即,经过若干次循环以后会回到我们需要的位置)
然后我们对于 也这样计算。随后我们分类讨论如何求得答案。
- 如果两个数的 均小于 ,那么, 必须满足 和 。那么,当且仅当 时有解,解是 。
- 如果只有一个数的 小于 ,不妨令 。那么,必定有 。那么,当且仅当 且 时有解,解是 。
- 如果没有一个数的 小于 ,那么, 必须满足:
那么对于第三种情况,我们定义变量 ,并赋值为满足条件1和3的最小值。很显然,此时 。
随后,我们不停地将 的值增加 (可知这样不会破坏条件1和3),直到其满足条件2。由于 最大只能为 ,所以不会超时。此时的 已经同时满足条件1,2和3。
最后我们再将 的值不停增加 (可知这样不会破坏条件1,2,3),直到 满足条件4(此时答案为 ),或者已经增加了超过 次(此时无解)。
综合所有情况,就是正解了。
代码#
注意千万不要把 y1
定义成全局变量!如果评测机编译器版本较老,这会和 math.h
冲突,造成错误。
// 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;
}
cpp评测记录:R25577582 ↗