C++之路进阶——codevs1281（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.要用快速幂。

代码：

 #include<cstdio>
 #include<iostream>
 #define ll long long

 using namespace std;

 long long m,a,c,x0,n,g;
 long long x[][],b[][],f[][];

 long long mull(long long a,long long b,long long m)
      {
          long long ans=;
          while (b)
            {
                if (b&) ans=(a+ans)%m;
                b>>=;
                a=(a<<)%m;
            }
          return ans;
      }

 int mull1 (long long a[][],long long b[][],long long ans[][])
      {
         long long c[][];
          for (int i=;i<;i++)
             for (int j=;j<;j++)
              {
                  c[i][j]=;
               for (int k=;k<;k++)
                 c[i][j]=(c[i][j]+mull(a[i][k],b[k][j],m))%m;
               }
           for (int i=;i<;i++)
             for (int j=;j<;j++)
             ans[i][j]=c[i][j];
      }

 int mull2 (long long a[][],long long b[][],long long ans[][])
      {
          long long c[][];
          for (int i=;i<;i++)
             for (int j=;j<;j++)
                {
                    c[i][j]=;
                    for (int k=;k<;k++)
                    c[i][j]=(c[i][j]+mull(a[i][k],b[k][j],m))%m;
                }
            for (int i=;i<;i++)
              ans[][i]=c[][i];
      }

 int main()
    {
         scanf("%lld%lld%lld%lld%lld%lld",&m,&a,&c,&x0,&n,&g);
         x[][]=a;
      x[][]=x[][]=;
      b[][]=b[][]=;
      f[][]=x0;f[][]=c;
      while (n)
        {
             if (n&) mull1(x,b,b);
               mull1(x,x,x);
               n>>=;
        }
        mull2(f,b,f);
        printf("%lld\n",f[][]%g);
         return ;
    }