GHOJ 311 两个数

题目描述

现有两个人，若第一个人当前手中的数为w1，则下一秒他手上的数将会变成（x1×w1+y1）mod m；若第二个人当前手中的数为w2,则下一秒他手上的数将会变为（x2×w2+y2）mod m（a mod b表示a除以b的余数）。第0秒,两个人手上的数分别为h1，h2；请求出最快在第几秒，第一个人手上的数为a1，且第二个人手上的数为a2。若不可能，则输出-1。

输入输出格式

输入格式

第一行为一个正整数T，表示数据组数。

对于接下来的每一组数据，第一行为一个正整数m，第二行包括两个整数h1，a1，第三行包括两个整数x1，y1，第四行包括两个整数h2，a2，第五行包括两个整数x2，y2。

输出格式

对于每一组数据，输出一行，一个整数，如题所述。

输入输出样例

输入样例

4 2

1 1

0 1

2 3

1023

1 2

1 0

1 2

1 1

输出样例

-1

说明

数据规模

对于30%的数据，m≤1000；

对于100%的数据，T≤5，h1不等于a1且h2不等于a2，2≤m≤10^6，0≤h1,a2，x1，y1，h2，a2，x2，y2＜m。

题解

此题的关键在于找h变化的循环节，暴力查找即可。找到之后就判断循环节组合起来是否长度相同即可。具体看程序理解。

#include <iostream>
#include <cstring>

#define MAXM 1000000

using namespace std;

int T;
long long m;
long long h, a, x, y;
long long num[2][2];
int b[MAXM];

int main()
{
    cin >> T;
    while(T--)
    {
        cin >> m;
        for(register int i = 0; i < 2; ++i)
        {
            cin >> h >> a >> x >> y;
            num[i][0] = 0;
            num[i][1] = 1;
            if(h != a)
            {
                memset(b, 0, sizeof(int) * m);
                b[h] = 1;
                while(h != a)
                {
                    ++num[i][0];
                    h = (h * x + y) % m;
                    if(b[h])
                    {
                        num[i][0] = -1;
                        break;
                    }
                    b[h] = 1;
                }
            }
            memset(b, 0, sizeof(int) * m);
            h = (h * x + y) % m;
            b[h] = 1;
            while(h != a)
            {
                ++num[i][1];
                h = (h * x + y) % m;
                if(b[h])
                {
                    num[i][1] = -1;
                    break;
                }
                b[h] = 1;
            }
        }
        if(num[0][0] == -1 || num[1][0] == -1) cout << -1;
        else if(num[0][0] == num[1][0]) cout << num[0][0];
        else if(num[0][1] == -1 && num[1][1] == -1) cout << -1;
        else if(num[0][1] == -1)
        {
            if(num[0][0] < num[1][0]) cout << -1;
            else if((num[0][0] - num[1][0]) % num[1][1]) cout << -1;
            else cout << num[0][0];
        }
        else if(num[1][1] == -1)
        {
            if(num[1][0] < num[0][0]) cout << -1;
            else if((num[1][0] - num[0][0]) % num[0][1]) cout << -1;
            else cout << num[1][0];
        }
        else
        {
            long long g1 = num[0][1], g2 = num[1][1], g3;
            while(g2)
            {
                g3 = g1 % g2;
                g1 = g2;
                g2 = g3;
            }
            if((num[0][0] - num[1][0]) % g1) cout << -1;
            else for(register int i = 0; ; ++i)
            {
                if(num[0][0] + num[0][1] * i < num[1][0]) continue;
                if(!((num[0][0] + num[0][1] * i - num[1][0]) % num[1][1]))
                {
                    cout << num[0][0] + num[0][1] * i;
                    break;
                }
            }
        }
        cout << "
";
    }
    return 0;
}

参考程序