time limit per test1 second
memory limit per test256 megabytes
inputstandard input
outputstandard output
Mike has a frog and a flower. His frog is named Xaniar and his flower is named Abol. Initially(at time 0), height of Xaniar is h1 and height of Abol is h2. Each second, Mike waters Abol and Xaniar.
So, if height of Xaniar is h1 and height of Abol is h2, after one second height of Xaniar will become and height of Abol will become where x1, y1, x2 and y2 are some integer numbers and denotes the remainder of a modulo b.
Mike is a competitive programmer fan. He wants to know the minimum time it takes until height of Xania is a1 and height of Abol is a2.
Mike has asked you for your help. Calculate the minimum time or say it will never happen.
Input
The first line of input contains integer m (2 ≤ m ≤ 106).
The second line of input contains integers h1 and a1 (0 ≤ h1, a1 < m).
The third line of input contains integers x1 and y1 (0 ≤ x1, y1 < m).
The fourth line of input contains integers h2 and a2 (0 ≤ h2, a2 < m).
The fifth line of input contains integers x2 and y2 (0 ≤ x2, y2 < m).
It is guaranteed that h1 ≠ a1 and h2 ≠ a2.
Output
Print the minimum number of seconds until Xaniar reaches height a1 and Abol reaches height a2 or print -1 otherwise.
Examples
input
5
4 2
1 1
0 1
2 3
output
3
input
1023
1 2
1 0
1 2
1 1
output
-1
Note
In the first sample, heights sequences are following:
Xaniar:
Abol:
【题目链接】:http://codeforces.com/contest/548/problem/C
【题解】
对m取余；很容易想到会有循环节;
(操作的是同一个数字!且x1,y1不变！)
那么就看一下h1什么时候会变成a1,时间记为num1,然后再让a1变成a1看看时间为多少记为xun1;
同理搞出num2和xun2;
t = num1+x*xun1 == num2 + y*xun2;
找到符合要求的最小的t就好;
这里我们可以枚举x;;
((num1+x*xun1)-num2)%xun2
->(x*xun1+num1-num2)%xun2
=(x*xun1)%xun2 + (num1-num)%xun2
=(((x%xun2)*(xun1%xun2))%xun2+(num1-num)%xun2);
要让上面这个等于0
xun2是小于m的,
所以如果x大于m之后(x%xun2)肯定就会出现循环节;
而xun1%xun2是定值(num1-num)%xun2也是定值
所以x的话最多也就枚举到m吧.如果还不能整除就没办法了;
因为x是顺序枚举的,所以自然所得的t也是最小的;
有可能会出现没有循环节的情况,就是a1不能再变成a1了;特判一下.
比如y==0的时候,h变成0了,则就不会再出现循环节了;
【完整代码】
#include <bits/stdc++.h>
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define LL long long
#define rep1(i,a,b) for (int i = a;i <= b;i++)
#define rep2(i,a,b) for (int i = a;i >= b;i--)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define rei(x) scanf("%d",&x)
#define rel(x) scanf("%I64d",&x)
typedef pair<int,int> pii;
typedef pair<LL,LL> pll;
//const int MAXN = x;
const int dx[9] = {0,1,-1,0,0,-1,-1,1,1};
const int dy[9] = {0,0,0,-1,1,-1,1,-1,1};
const double pi = acos(-1.0);
int m;
LL h1,a1,x1,y1;
LL h2,a2,x2,y2;
LL num1,xun1,num2,xun2;
int main()
{
//freopen("F:\rush.txt","r",stdin);
rei(m);
rel(h1);rel(a1);
rel(x1);rel(y1);
rel(h2);rel(a2);
rel(x2);rel(y2);
LL h = h1;
rep1(i,1,2*m)
{
h = (x1*h+y1)%m;
if (h==a1)
if (num1==0)
{
num1 = i;
}
else
{
xun1 = (i-num1);
break;
}
}
h = h2;
rep1(i,1,2*m)
{
h = (x2*h+y2)%m;
if (h==a2)
if (num2 == 0)
num2 = i;
else
{
xun2 = i-num2;
break;
}
}
if (num1==0 || num2==0)
{
puts("-1");
return 0;
}
if (xun1==0 && xun2==0)
{
if (num1==num2)
printf("%I64d
",num1);
else
puts("-1");
return 0;
}
rep1(i,0,m)
{
if (xun1==0)
{
if (num2+i*xun2==num1)
{
printf("%I64d
",num1);
return 0;
}
}
else
if (xun2==0)
{
if (num1+i*xun1==num2)
{
printf("%I64d
",num2);
return 0;
}
}
else
if (num1+1LL*i*xun1>=num2 && ((num1+i*xun1-num2)%xun2)==0)
{
printf("%I64d
",num1+1LL*i*xun1);
return 0;
}
}
puts("-1");
return 0;
}