2015年5月28日 星期四

2015/05/28 Codeforces 547A. Mike and Frog

/*
    算出第一次 出現A0,A1需要多久 (S0,S1)
    以及再次出現需要多久 (D0, D1)

    接下來 列方程式
    枚舉求解
*/
// http://codeforces.com/problemset/problem/547/A
#include <iostream>
#include <cstdio>

using namespace std;

typedef long long ll;

int M;
int H[2], A[2], X[2], Y[2];

int ask(int s, int e, int i)
{
    for(int Mi = 1; Mi <= M; Mi++)
    {
        s = ((ll)s*X[i]+Y[i] )%M;
        if( s == e ) return Mi;
    }

    return -1;
}

int gcd(int x, int y)
{
    while( x && y )
    {
        if( x < y ) swap(x, y);
        x %= y;
    }

    return x+y;
}

int S[2], D[2];

int main()
{
    scanf("%d", &M);

    for(int i = 0; i < 2; i++)
        scanf("%d %d %d %d", &H[i], &A[i], &X[i], &Y[i]);

    for(int i = 0; i < 2; i++)
    {
        S[i] = ask(H[i], A[i], i);
        D[i] = ask(A[i], A[i], i);

        if( S[i] == -1 )
        {
            puts("-1");
            return 0;
        }
    }

    if( S[0] == S[1] ){ cout<<S[0]<<endl; return 0; }
    else if( S[1] > S[0] && D[0] != -1 && (S[1]-S[0])%D[0] == 0  ){ cout<<S[1]<<endl; return 0; }
    else if( S[1] < S[0] && D[1] != -1 && (S[0]-S[1])%D[1] == 0  ){ cout<<S[0]<<endl; return 0; }
    else if( D[0] == -1 || D[1] == -1 ){ puts("-1"); return 0; }

    // solve equation S[0]+D[0]*x == S[1]+D[1]*y
    // Ax = B (MOD C)

    int A = D[0];
    int B = S[1]-S[0];
    int C = D[1];

    B = (B%C+C)%C;

    for(int Ci = 0; Ci < C; Ci++)
    {
        if( (ll)A*Ci%C == B )
        {
            int p = Ci;

            while( S[0]+(ll)D[0]*p < S[1] )
                p += C/gcd(A, C);

            cout<<S[0]+(ll)D[0]*p<<endl;
            return 0;
        }


    }

    puts("-1");
}

沒有留言:

張貼留言