记录编号	89609	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOI 2012]随机数生成器	最终得分	100
用户昵称	noip	是否通过	通过
代码语言	C++	运行时间	0.006 s
提交时间	2014-03-03 08:12:38	内存使用	0.31 MiB

#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<string>
#include<cmath>
#include<cctype>
#include<ctime>
using namespace std;
const int maxlongint=2147483647;
const int inf=1000000000;
unsigned long long mod;
unsigned long long ksc(unsigned long long a,unsigned long long b)
{
	if(a<b)
		swap(a,b);
	unsigned long long c=0,d=a;
	for(;b;b=b>>1)
	{
		if(b&1)
			c=(c+d)%mod;
		d=(d+d)%mod;
	}
	return c;
}
struct matrix
{
	unsigned long long d[3][3];
};
matrix jzc(matrix a,matrix b)
{
	matrix c;
	memset(c.d,0,sizeof(c.d));
	for(int i=1;i<=2;i++)
		for(int j=1;j<=2;j++)
			for(int k=1;k<=2;k++)
				c.d[i][j]=(c.d[i][j]+ksc(a.d[i][k],b.d[k][j]))%mod;
	return c;
}
matrix jzm(matrix a,unsigned long long b)
{
	matrix c,d=a;
	c.d[1][1]=c.d[2][2]=1;
	c.d[1][2]=c.d[2][1]=0;
	for(;b;b=b>>1)
	{
		if(b&1)
			c=jzc(c,d);
		d=jzc(d,d);
	}
	return c;
}
int main()
{
	freopen("randoma.in","r",stdin);
	freopen("randoma.out","w",stdout);	
	unsigned long long a,c,x0,n,g;
	cin>>mod>>a>>c>>x0>>n>>g;
	matrix k;
	k.d[1][1]=a;
	k.d[1][2]=c;
	k.d[2][1]=0;
	k.d[2][2]=1;
	k=jzm(k,n);
	unsigned long long p=(ksc(x0,k.d[1][1])+k.d[1][2])%mod;
	cout<<p%g;
}