????1281 Xn????
???????????: 1 s
???????????: 128000 KB
?????????? : ??? Master
??????????? Description
????????6??????m?? a?? c?? x0?? n?? g
????Xn+1 = ( aXn + c ) mod m????Xn
????m?? a?? c?? x0?? n?? g<=10^18
???????????? Input Description
????????????? m?? a?? c?? x0?? n?? g
??????????? Output Description
???????????? Xn mod g
???????????? Sample Input
????11 8 7 1 5 3
??????????? Sample Output
????2
?????????Χ????? Data Size & Hint
????int64??λ???????????????
???????
????1.????????????
????2.???? {??a??0????1??1??}??{Xn??c}
????3.?????????
????????

1 #include<cstdio>
2 #include<iostream>
3 #define ll long long
4
5 using namespace std;
6
7 long long m??a??c??x0??n??g;
8 long long x[2][2]??b[2][2]??f[1][2];
9
10 long long mull(long long a??long long b??long long m)
11      {
12          long long ans=0;
13          while (b)
14            {
15                if (b&1) ans=(a+ans)%m;
16                b>>=1;
17                a=(a<<1)%m;
18            }
19          return ans;
20      }
21
22 int mull1 (long long a[2][2]??long long b[2][2]??long long ans[2][2])
23      {
24         long long c[2][2];
25          for (int i=0;i<2;i++)
26             for (int j=0;j<2;j++)
27              {
28                  c[i][j]=0;
29               for (int k=0;k<2;k++)
30                 c[i][j]=(c[i][j]+mull(a[i][k]??b[k][j]??m))%m;
31               }
32           for (int i=0;i<2;i++)
33             for (int j=0;j<2;j++)
34             ans[i][j]=c[i][j];
35      }
36
37 int mull2 (long long a[1][2]??long long b[2][2]??long long ans[1][2])
38      {
39          long long c[1][2];
40          for (int i=0;i<1;i++)
41             for (int j=0;j<2;j++)
42                {
43                    c[i][j]=0;
44                    for (int k=0;k<2;k++)
45                    c[i][j]=(c[i][j]+mull(a[i][k]??b[k][j]??m))%m;
46                }
47            for (int i=0;i<2;i++)
48              ans[0][i]=c[0][i];
49      }
50
51 int main()
52    {
53         scanf("%lld%lld%lld%lld%lld%lld"??&m??&a??&c??&x0??&n??&g);
54         x[0][0]=a;
55      x[1][0]=x[1][1]=1;
56      b[0][0]=b[1][1]=1;
57      f[0][0]=x0;f[0][1]=c;
58      while (n)
59        {
60             if (n&1) mull1(x??b??b);
61               mull1(x??x??x);
62               n>>=1;
63        }
64        mull2(f??b??f);
65        printf("%lld
"??f[0][0]%g);
66         return 0;
67    }