codeforces547a

http://codeforces.com/contest/547/problem/A

题意：确定是否在某一时刻高度都同时为a1和a2。

step1:找到青蛙首次到a1的时间pri1以及重复到a1的周期t1。对花也这样得到pri2,t2。

step2:转为求使pri1+x*t1=pri2+y*t2的最小正的x和y。移项变为x*t1-y*t2=pri2-pri1。记为x1*t1+y1*t2=c（2式）

step3:先将c，x1,y1都加上绝对值，代exgcd的模板。

step4:由于exgcd得到的是等式右边=gcd时的解，因此将算出来的x1,y1乘以c/gcd，得到满足2式的x1,y1，顺带去掉了c的绝对值的影响。此时的x1,y1仍可使2式成立。注意x和y都要>=0因为青蛙只有首次，第二次，第三次到a1高度，而没有第负数次到a1。如果是标准的拓展欧几里得,ax+by=c,x增加y要减少才能使等式成立。但是在ax-by=c中，x,y同时增大或减小才能成立。

step5:接下来要调x,y的大小,得到的y1乘-1变为实际的y。

step6:由于x,y可能是负数，x可增加任意倍的incx:t2/gcd,y加incy:t1/gcd。那么如果x<,让x加|x/incx|*incx。如果不整除还要多加一次。注意要使等式仍成立，y也要加。

step7:如果y小于0,同step5

step8:保证x,y还是最小的

其他的没了，有个数据找不到周期，特判。

本题周期为正数，因此公式还算简单。如果a,b一正一负。。。。。。

//#pragma comment(linker,"/STACK:1024000000,1024000000")

#include<iostream>

#include<cstdio>

#include<string>

#include<cstring>

#include<vector>

#include<cmath>

#include<queue>

#include<stack>

#include<map>

#include<set>

#include<algorithm>

#include <stack>

#include <list>

using namespace std;

const int SZ=,INF=0x7FFFFFFF;

typedef long long lon;

lon exgcd(lon a,lon b,lon &x,lon &y,lon &d)

  {

       if(b==)

      {

          x=;

         y=;

         d=a;

         return a;

     }

     lon gcd=exgcd(b,a%b,x,y,d);

    lon x2=x,y2=y;

   x=y2;

   y=x2-(a/b)*y2;

    return gcd;

}

int main()

{

    std::ios::sync_with_stdio();

    //freopen("d:\\1.txt","r",stdin);

    lon m;

    cin>>m;

    lon h1,a1,x1,y1,h2,a2,x2,y2;

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

    set<pair<lon,lon>> st;

    st.insert(make_pair(h1,h2));

    lon cnt1=,cnt2=,pri1=,pri2=,t1=,t2=;

    for(lon time=;;++time)

    {

        lon newa1=(x1*h1+y1)%m,newa2=(x2*h2+y2)%m;

        if(newa1==a1)

        {

            if(cnt1==)pri1=time;

            else if(cnt1==) t1=time-pri1;

            ++cnt1;

        }

        if(newa2==a2)

        {

            if(cnt2==)pri2=time;

            else if(cnt2==)t2=time-pri2;

            ++cnt2;

        }

        if(pri1&&pri2&&t1&&t2)break;

        if(newa1==a1&&newa2==a2)

        {

            cout<<time<<endl;

            return ;

        }

        if(time>1e7)

        {

            cout<<-<<endl;

            return ;

        }

        h1=newa1,h2=newa2;

    }

    lon x,y,d;

    exgcd(abs(t1),abs(t2),x,y,d);

    if(abs(pri1-pri2)%d==)

    {

        x*=(pri2-pri1)/d;

        y*=(pri2-pri1)/d;

        y*=-;

        if(x<)

        {

            int beishu=abs((x)/(t2/d));

            x=x+beishu*abs(t2/d);

            y=y+beishu*abs(t1/d);

        }

        if(y<)

        {

            int num=;

            num=abs((y)/(t1/d));

            y=y+num*abs(t1/d);

            if(y<)

            {

                ++num;

                y+=abs(t1/d);

            }

            x+=num*abs(t2/d);

        }

        if(x<)x+=abs(t2/d);

        if(x>&&y>)

        {

            int num1=abs((x)/(t2/d));

            int num2=abs((y)/(t1/d));

            int miner=min(num1,num2);

            x-=miner*abs(t2/d);

            y-=miner*abs(t1/d);

        }

        cout<<pri1+x*t1<<endl;

    }

    else cout<<-<<endl;

    return ;

}

可暴力搜索，得到起点和周期后，小的一方加上周期，直到相等。相等值即为结果。