C++之路进阶??矩阵乘法（Xn数列）

　　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    }