Xn数列

题目描述 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

#include<iostream>

using namespace std;

struct node{

long long v[][];

}t,tt;long long a,c,m,n,x,g;

long long quick_mult(long long a,long long b,long long mod)

{

long long re=;

while(a)

{

if(a&)re=(re+b)%mod;

b=(b+b)%mod;

a>>=;

}

  return re;

}

node ju(node a,node b)

{

node re;

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

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

  {

  re.v[i][j]=;

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

  re.v[i][j]+=quick_mult(a.v[i][k],b.v[k][j],m);

  re.v[i][j]%=m;

  }

return re;

}

long long ans()

{

node re=tt,r=t;

while(n)

{

if(n&)re=ju(re,r);

r=ju(r,r);

n>>=;

}

return re.v[][]%g;

}

int main()

{

scanf("%lld%lld%lld%lld%lld%lld",&m,&a,&c,&x,&n,&g);

t.v[][]=a%m;

t.v[][]=;

t.v[][]=c%m;

t.v[][]=;

tt.v[][]=x%m;

tt.v[][]=;

tt.v[][]=;

tt.v[][]=;

cout<<ans()<<endl;

return ;

 }

这个题目用到的内容矩阵乘法快速幂快速乘
矩阵乘法略
快速幂
使用二进制进行多次乘几倍底数减少运算量
int pow4(int a,int b){

int r=1,base=a;

while(b){

if(b&1) r*=base;

base*=base;

b>>=1;

}

return r;

}
快速乘和快速幂差不多的结构用来解决 2个longlong型整数相乘取余的问题
如果两个longlong类型的整数直接相乘可能会溢出
使用加法一边加一遍取余则会减小溢出的可能
采用和快速幂一样的方法快速处理并取余
long long quick_mult(long long a,long long b,long long mod)

{

long long re=0;

while(a)

{

if(a&1)re=(re+b)%mod;

b=(b+b)%mod;

a>>=1;

}

return re;

}

巴特西

Xn数列

最新文章

热门文章