给你6个数，m, a, c, x0, n, g

Xn+1 = ( aXn + c ) mod m，求Xn

m, a, c, x0, n, g<=10^18

包含6个用空格分割的m,a,c,X0,n和g，其中a,c,X0是非负整数，m,n,g是正整数。

输出一个数，即Xn mod g

11 8 7 1 5 3

2

 

构造矩阵

转移矩阵

|a0 0|  

|1  1|  

初始矩阵

|x0 C|

 #include<cstdio>

 #define ll long long

 ll z[][],a[][];

 ll m,b,c,x0,n,p;

 ll plus(ll x,ll y,ll p){

     ll s=;

     while (x>=){

         if (x&==) s=(s+y)%p;

          x=x>>;

          y=(y+y)%p;

     }

     return s;

 }

 void mult1(ll a[][],ll b[][]){

     ll c[][];

     for (int i=;i<;i++) for (int j=;j<;j++) c[i][j]=;

     for (int i=;i<;i++)

         for (int j=;j<;j++)

             for (int k=;k<;k++)

                 c[i][j]=(c[i][j]+plus(a[i][k],b[k][j],p))%p;

     for (int i=;i<;i++) for (int j=;j<;j++) a[i][j]=c[i][j];

 }

 void mult2(ll a[][],ll b[][]){

     ll c[][];

     for (int i=;i<;i++) for (int j=;j<;j++) c[i][j]=;

     for (int i=;i<;i++)

         for (int j=;j<;j++)

             for (int k=;k<;k++)

                 c[i][j]=(c[i][j]+plus(a[i][k],b[k][j],p))%p;

     for (int i=;i<;i++) for (int j=;j<;j++) a[i][j]=c[i][j];

 }

 void pow(ll z[][],ll n){

     ll ans[][];

     for (int i=;i<;i++) for (int j=;j<;j++) ans[i][j]=;

     ans[][]=; ans[][]=;

     while (n>){

         if (n%==) mult1(ans,z);

         n=n>>;

         mult1(z,z);

     }

     for (int i=;i<;i++) for (int j=;j<;j++) z[i][j]=ans[i][j];

 }

 int main(){

     scanf("%lld%lld%lld%lld%lld%lld",&p,&b,&c,&x0,&n,&m);

     z[][]=b;z[][]=;z[][]=;

     a[][]=x0;a[][]=c;

     pow(z,n);

     mult2(a,z);

     printf("%lld",a[][]%m);

 }