「日常训练」 Mike and Frog (CFR305D2C)

题意与分析 （Codeforces 548C）

我开始以为是一条数学题，死活不知道怎么做，无奈看题解，才知这是一条暴力，思维江化了- -

题意大概是这样的：

两个东西的初始高度分别为h1,h2" role="presentation">h1,h2h1,h2，每秒二者的高度分别变化为(x1h1+y1)%m1" role="presentation">(x1h1+y1)%m1(x1h1+y1)%m1与(x2h2+y2)%m2" role="presentation">(x2h2+y2)%m2(x2h2+y2)%m2，问几秒后二者高度达到各自的目标a1,a2" role="presentation">a1,a2a1,a2，如果不能输出-1。

实际上我看了题解还是不能明白为什么迭代2m" role="presentation">2m2m次，或者说2*…这个变量为什么是m。2这个系数能够理解，我们需要找出循环节；但是为什么是m看了半天还是不能明白。我去看看扩展gcd算法的相关题目来找找思路。

总而言之，迭代这么多次，如果他们不能达到各自的目标输出-1。否则一定有解。我们前面的系数2保证了至少能达到2次a" role="presentation">aa，然后找到其中的周期，之后暴力跑一段（取一个很大的数字，我这里有可能被hack），看能不能达到一致即可。

不能输出-1。

总而言之，这是用到了数学结论、披着数学外衣、但是本质是暴力的一道题目。希望自己能够将暴力和数学融会贯通。

代码

#include <bits/stdc++.h>

#define MP make_pair

#define PB push_back

#define fi first

#define se second

#define ZERO(x) memset((x), 0, sizeof(x))

#define ALL(x) (x).begin(),(x).end()

#define rep(i, a, b) for (int i = (a); i <= (b); ++i)

#define per(i, a, b) for (int i = (a); i >= (b); --i)

#define QUICKIO                  \

    ios::sync_with_stdio(false); \

    cin.tie(0);                  \

    cout.tie(0);

using namespace std;

using ll = long long;

using ull = unsigned long long;

using pi = pair<int,int>;

const int MAXN=500;

// After reading the editorial.

int main()

{

QUICKIO

    ll m,h1,a1,x1,y1,h2,a2,x2,y2;

    cin>>m>>h1>>a1>>x1>>y1>>h2>>a2>>x2>>y2;

    ll start1=h1,start2=h2;

    vector<ll> time1,time2;

    rep(i,0,2*m) // why 2*m? we need a zhouqi!

    {

        if(start1==a1)

            time1.PB(i);

        if(start2==a2)

            time2.PB(i);

        start1=(start1*x1+y1)%m;

        start2=(start2*x2+y2)%m;

    }

    if(time1.size()==0 || time2.size()==0)

    {

        cout<<"-1"<<endl;

        return 0;

    }

    ll  period1=time1[1]-time1[0],

        period2=time2[1]-time2[0],

        go1=time1[0],

        go2=time2[0];

    //cout<<period1<<" "<<period2<<" "<<go1<<" "<<go2<<endl;

    rep(i,1,2*m) // I dont know why 2m O_O

    {

        if(go1==go2)

        {

            cout<<go1<<endl;

            return 0;

        }

        if(go1<go2)

            go1+=period1;

        else go2+=period2;

    }

    cout<<-1<<endl;

    return 0;

}