数论/暴力 Codeforces Round #305 (Div. 2) C. Mike and Frog

题目传送门

 /*
     数论/暴力：找出第一次到a1,a2的次数，再找到完整周期p1,p2，然后以2*m为范围
                 t1,t2为各自起点开始“赛跑”，谁落后谁加一个周期，等到t1 == t2结束
     详细解释：http://blog.****.net/u014357885/article/details/46044287
 */
 #include <cstdio>
 #include <algorithm>
 #include <cstring>
 #include <iostream>
 using namespace std;

 typedef long long ll;

 const int MAXN = 1e3 + ;
 const int INF = 0x3f3f3f3f;

 int main(void)        //Codeforces Round #305 (Div. 2) C. Mike and Frog
 {
     int m;
     ll h1, a1, x1, y1, h2, a2, x2, y2;
     while (scanf ("%d%I64d%I64d%I64d%I64d%I64d%I64d%I64d%I64d", &m, &h1, &a1, &x1, &y1, &h2, &a2, &x2, &y2) == )
     {
         ll t1 = -, t2 = -, p1 = -, p2 = -;
         for (int i=; i<=m; ++i)                //get t1, p1
         {
             h1 = (h1 * x1 + y1) % m;
             if (h1 == a1)    {t1 = i; break;}
         }
         if (t1 == -)    {puts ("-1"); continue;}
         for (int i=; i<=m; ++i)
         {
             h1 = (h1 * x1 + y1) % m;
             if (h1 == a1)    {p1 = i; break;}
         }

         for (int i=; i<=m; ++i)                //get t2, p2
         {
             h2 = (h2 * x2 + y2) % m;
             if (h2 == a2)    {t2 = i; break;}
         }
         if (t2 == -)    {puts ("-1"); continue;}
         for (int i=; i<=m; ++i)
         {
             h2 = (h2 * x2 + y2) % m;
             if (h2 == a2)    {p2 = i; break;}
         }

         bool ok = false;                        //get t1 == t2
         for (int i=; i<=*m; ++i)
         {
             if (t1 == t2)    {ok = true; printf ("%I64d\n", t1);    break;}
             if (t1 < t2)    t1 += p1;
             else    t2 += p2;
         }
         if (!ok)    puts ("-1");
     }

     return ;
 }

 /*
 5
 4 2
 1 1
 0 1
 2 3
 1023
 1 2
 1 0
 1 2
 1 1
 */