题目描述 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按位相乘可以不要用高精度。
正解：矩阵快速幂+矩阵乘法
解题报告：
对于一个递推式，求某一项的值。
这显然是可以矩阵乘法的，用一下快速幂就可以了。但是注意一点，因为对于long long下的乘法很有可能会乘炸，所以我们需要用加法模拟一下乘法（快速幂的形式），就可以啦。
代码如下：
1 //It is made by jump~ 2 #include <iostream> 3 #include <cstdlib> 4 #include <cstring> 5 #include <cstdio> 6 #include <cmath> 7 #include <algorithm> 8 #include <ctime> 9 #include <vector> 10 #include <queue> 11 #include <map> 12 #include <set> 13 using namespace std; 14 typedef long long LL; 15 LL MOD,A,C,n,g; 16 struct matrix{ 17 LL a[2][2]; 18 }ans,init; 19 20 inline LL getlong() 21 { 22 LL w=0,q=0; char c=getchar(); 23 while((c<'0' || c>'9') && c!='-') c=getchar(); if(c=='-') q=1,c=getchar(); 24 while (c>='0' && c<='9') w=w*10+c-'0', c=getchar(); return q ? -w : w; 25 } 26 27 inline LL quick_cj(LL x,LL y){//为防止溢出，用快速幂的方法，用加法代替乘法 28 LL da=0; 29 while(y>0) { 30 if(y&1) da+=x,da%=MOD; 31 x+=x; x%=MOD; 32 y>>=1; 33 } 34 return da; 35 } 36 37 inline matrix cj(matrix a,matrix b){ 38 matrix c=init; 39 for(int i=0;i<2;i++) 40 for(int j=0;j<2;j++) 41 for(int k=0;k<2;k++) 42 c.a[i][j]+=quick_cj(a.a[i][k],b.a[k][j]),c.a[i][j]%=MOD; 43 return c; 44 } 45 46 inline matrix mul(LL x){ 47 matrix base,tmp; tmp=base=init; 48 tmp.a[0][0]=1; tmp.a[1][1]=1; 49 base.a[0][0]=A; base.a[0][1]=0; 50 base.a[1][0]=base.a[1][1]=1; 51 while(x>0) { 52 if(x&1) tmp=cj(tmp,base); 53 base=cj(base,base); 54 x>>=1; 55 } 56 return tmp; 57 } 58 59 inline void work(){ 60 MOD=getlong(); A=getlong(); C=getlong(); 61 ans.a[0][0]=getlong(); ans.a[0][1]=C; n=getlong(); g=getlong(); 62 for(int i=0;i<2;i++) for(int j=0;j<2;j++) init.a[i][j]=0; 63 ans=cj(ans,mul(n)); 64 printf("%lld",ans.a[0][0]%g); 65 } 66 67 int main() 68 { 69 work(); 70 return 0; 71 }