题目描述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按位相乘可以不要用高精度。
题目分析
典型的矩阵快速幂问题。由递推式 Xn+1 = ( aXn + c ) mod m 可以构造出矩阵方程:
那么题目所求就可转化为一个1*2矩阵与n个二阶方阵的矩阵链乘。根据矩阵乘法的结合律,可得出:
即可转化为矩阵快速幂问题。其中的乘法运算已改为了倍增取模乘法。
1 //WikiOI 1281 Xn数列
2 #include <iostream>
3 using namespace std;
4 typedef long long LL;
5 LL m, a, c, x0, n, MOD;
6 LL mlti(LL a, LL b) //倍增取模乘法
7 {
8 a %= m;
9 LL ans = ;
while(b)
{
if(b & )ans = (ans + a)% m;
a = (a << )% m;
b >>= ;
}
return ans;
}
struct Matrix2
{
LL val[][];
Matrix2(LL k1,LL k2,LL k3,LL k4)
{
val[][] = k1; val[][] = k2; val[][] = k3; val[][] = k4;
}
void Mlti(Matrix2 &m) //矩阵乘法
{
LL v1 = mlti(val[][],m.val[][])+mlti(val[][],m.val[][]);
LL v2 = mlti(val[][],m.val[][])+mlti(val[][],m.val[][]);
LL v3 = mlti(val[][],m.val[][])+mlti(val[][],m.val[][]);
LL v4 = mlti(val[][],m.val[][])+mlti(val[][],m.val[][]);
val[][] = v1,val[][] = v2,val[][] = v3,val[][] = v4;
}
};
int main()
{
ios::sync_with_stdio(); //感谢陈思学长!
cin >>m >>a >>c >>x0 >>n >>MOD;
Matrix2 M(a, , , );
Matrix2 ans = M;
n -= ;
while(n)
{
if(n & ) ans.Mlti(M);
M.Mlti(M);
n >>=;
}
cout << ((mlti(x0, ans.val[][])+mlti(c, ans.val[][]))%m)%MOD;
return ;
}
那么题目所求就可转化为一个1*2矩阵与n个二阶方阵的矩阵链乘。根据矩阵乘法的结合律,可得出:
即可转化为矩阵快速幂问题。其中的乘法运算已改为了倍增取模乘法。
1 //WikiOI 1281 Xn数列
2 #include <iostream>
3 using namespace std;
4 typedef long long LL;
5 LL m, a, c, x0, n, MOD;
6 LL mlti(LL a, LL b) //倍增取模乘法
7 {
8 a %= m;
9 LL ans = ;
while(b)
{
if(b & )ans = (ans + a)% m;
a = (a << )% m;
b >>= ;
}
return ans;
}
struct Matrix2
{
LL val[][];
Matrix2(LL k1,LL k2,LL k3,LL k4)
{
val[][] = k1; val[][] = k2; val[][] = k3; val[][] = k4;
}
void Mlti(Matrix2 &m) //矩阵乘法
{
LL v1 = mlti(val[][],m.val[][])+mlti(val[][],m.val[][]);
LL v2 = mlti(val[][],m.val[][])+mlti(val[][],m.val[][]);
LL v3 = mlti(val[][],m.val[][])+mlti(val[][],m.val[][]);
LL v4 = mlti(val[][],m.val[][])+mlti(val[][],m.val[][]);
val[][] = v1,val[][] = v2,val[][] = v3,val[][] = v4;
}
};
int main()
{
ios::sync_with_stdio(); //感谢陈思学长!
cin >>m >>a >>c >>x0 >>n >>MOD;
Matrix2 M(a, , , );
Matrix2 ans = M;
n -= ;
while(n)
{
if(n & ) ans.Mlti(M);
M.Mlti(M);
n >>=;
}
cout << ((mlti(x0, ans.val[][])+mlti(c, ans.val[][]))%m)%MOD;
return ;
}