[CF547A] Mike and Frog

[CF547A] Mike and Frog - 数论

Description

有两个数 h1,h2，每次变化 h1=(h1*x1+y1)%m;h2=(h2*x2+y2)%m，经过 t 次变化，问你能否使得 h1=a1,h2=a2，如果可以就输出 t，否则输出 -1

Solution

求出起始位置和循环节，因为循环节显然是不会超过 m 的，所以我们可以暴力模拟，每次小的那边加，如果做了 2m 次还没有结果，那么就是无解

#include <bits/stdc++.h>
using namespace std;

#define int long long 

pair<int,int> solve(int m,int h,int a,int x,int y)
{
    int fir=0,cir=0;
    for(int i=1;i<=2*m;i++) 
    {
        h=(h*x+y)%m;
        if(h==a) 
        {
            if(fir==0) fir=i;
            else if(cir==0) cir=i-fir;
        }
    }
    return {fir,cir};
}

signed main()
{
    ios::sync_with_stdio(false);

    int m,h1,a1,x1,y1,h2,a2,x2,y2;
    cin>>m>>h1>>a1>>x1>>y1>>h2>>a2>>x2>>y2;
    
    auto pr1=solve(m,h1,a1,x1,y1);
    auto pr2=solve(m,h2,a2,x2,y2);

    int f1=pr1.first, f2=pr2.first;
    int c1=pr1.second, c2=pr2.second;

    if(f1&&f2)
        for(int i=1;i<=2*m;i++)
        {
            if(f1==f2) 
            {
                cout<<f1<<endl;
                return 0;
            }
            if(f1<f2) f1+=c1;
            else f2+=c2;
        }

    cout<<-1<<endl;
}