记录编号	152301	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOI 2012]随机数生成器	最终得分	100
用户昵称	HouJikan	是否通过	通过
代码语言	C++	运行时间	0.009 s
提交时间	2015-03-13 23:12:41	内存使用	0.32 MiB

#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <list>
#include <vector>
#include <ctime>
#include <functional>
#define pritnf printf
#define scafn scanf
#define sacnf scanf
#define For(i,j,k) for(int i=(j);i<=(k);(i)++)
#define Clear(a) memset(a,0,sizeof(a))
using namespace std;
typedef unsigned int Uint;
const int INF=0x3fffffff;
///==============struct declaration==============
unsigned long long quickmul(unsigned long long a,unsigned long long int b,unsigned long long Mod);
unsigned long long p,a,c,n,x0,g;
struct Matrixes{
   unsigned long long A[3][3];
   Matrixes (){memset(A,0,sizeof(A));}
   Matrixes operator *(const Matrixes &M) const{
      Matrixes res;
      for(int i=1;i<=2;i++)
         for(int j=1;j<=2;j++)
            for(int k=1;k<=2;k++){
               unsigned long long temp=quickmul(A[i][k],M.A[k][j],p);
               res.A[i][j]+=temp;
               res.A[i][j]%=p;
            }
      return res;
   }
};
///==============var declaration=================
const int MAXN=150050;
Matrixes Mul;
///==============function declaration============
Matrixes quickpow(Matrixes a,unsigned long long Exp);
///==============main code=======================
int main()
{
   freopen("randoma.in","r",stdin);
   freopen("randoma.out","w",stdout);
   scanf("%llu%llu%llu%llu%llu%llu",&p,&a,&c,&x0,&n,&g);
   a%=p,c%=p,x0%=p;
   Mul.A[1][1]=a;Mul.A[2][2]=1;Mul.A[2][1]=c;Mul.A[1][2]=0;
   Mul=quickpow(Mul,n);
   unsigned long long ans=(quickmul(Mul.A[1][1],x0,p)+Mul.A[2][1])%p;
   printf("%llu\n",ans%g);
   return 0;
}
///================fuction code====================
unsigned long long quickmul(unsigned long long a,unsigned long long int b,unsigned long long Mod){
   if (b==0) return 0;
   if (b==1) return a%Mod;
   unsigned  long long tmp=quickmul(a,b/2,Mod);
   tmp=(tmp*2)%Mod;
   if (b%2) tmp=(tmp+a)%Mod;
   return tmp;
}
Matrixes quickpow(Matrixes a,unsigned long long Exp){
   if (Exp==1) return a;
   Matrixes tmp=quickpow(a,Exp/2);
   tmp=tmp*tmp;
   if (Exp&1)
      tmp=a*tmp;
   return tmp;
}