小爱密码

序号：#137       难度：困难      时间限制：1000ms     内存限制：80M

描述

小爱同学有一个智能密码锁。锁上有九位数字，小爱同学每次会给A,B,C,D,mod,n六个正整数。 题目是这样的：

F(1) = A, F(2) = B

F(n) = F(n-1)*F(n-2)* C^D(n>2)

现在小爱同学想计算出 G(n) 的值（G(n)为F(n)的前n项积），并用该值作为密码锁的密码。

由于结果过大，所以答案 G(n)%mod

输入

 

多组数据。每组包含 6 个整数，分别代表 A, B, C, D, mod, n. (1<=A,B,C,D,mod,n<=1000000000)；数据组数不超过 2000.

 

输出

 

输出 G(n)%mod 的值。

答案保留 9 位有效数字，不足则补 0.

 

输入样例

2 2 2 2 1000 3
7 9 3 4 6 5

 复制样例

输出样例

000000064
000000003

题意：求F(n)的前n项积%mod，即题目里说的G(n)%mod

题解：写出几项后可以发现规律，乘积可以变成幂的指数相加形式，即最后可以变成A^x*B^b*(C^D)^z,主要是求x，y，z的过程，这样说太抽象了，看过程：

可以看出是一个求菲波那切数列的过程，不过数会很大，需要用到，欧拉降幂，即： A^X%mod=A^(X%get_euler(mod)+get_euler(mod))%mod，加mod是为了变成正的~~

上代码：

#include <iostream>
#include <cstring>
using namespace std;
typedef long long ll;
struct hh{
	ll a[4][4];
}x;
ll get_euler(ll n){//欧拉函数
	ll res=n,a=n;
	for (ll i = 2;  i*i <= a;i++){
		if(a%i==0){
			res=res/i*(i-1);
			while(a%i==0) a=a/i;
		}
	}
	if(a>1) res=res/a*(a-1);
	return res;
}
hh mul(hh a,hh b,ll c){//矩阵快速幂，用来求指数，即菲波那切数列
	hh w;
	memset(w.a,0,sizeof(w.a));//初始化别忘记
	for (int i = 0; i < 2;i++){
		for (int j = 0; j < 2; j++){
			for (int k = 0; k < 2;k++){
				w.a[i][j]=(w.a[i][j]+a.a[i][k]*b.a[k][j]%c)%c;
			}
		}
	}
	return w;
}
hh quick1(hh a,ll b,ll c){//矩阵快速幂，用来求指数，即菲波那切数列
	hh ans;
	memset(ans.a,0,sizeof(ans.a));//初始化别忘记
	for (int i = 0; i < 2; i++){
		ans.a[i][i]=1;
	}
	while(b){
		if(b&1) ans=mul(ans,a,c);
		b>>=1;
		a=mul(a,a,c);
	}
	return ans;
}
ll quick2(ll a,ll b,ll c){//数的快速幂，用来求C^D
	ll ans=1;
	a=a%c;
	while(b){
		if(b&1) ans=(ans*a)%c;
		b>>=1;
		a=(a*a)%c;
	}
	return ans%c;
}
int main(){
	ll a,b,c,d,mod,n,modd;
	while(cin >> a >> b >> c >> d >> mod >> n){
		modd=get_euler(mod);
		x.a[0][0]=1;x.a[0][1]=1;
		x.a[1][0]=1;x.a[1][1]=0;//初始化别忘记
		hh w1=quick1(x,n,modd);//记住modd和mod别用错了，求a的指数
		hh w2=quick1(x,n+1,modd);//记住modd和mod别用错了，求b的指数
		ll aaa=w1.a[1][0]+modd;//记住modd和mod别用错了，求a的指数
		ll bbb=w2.a[1][0]-1+modd;//记住modd和mod别用错了，求b的指数
		ll ccc=aaa+bbb-n%modd+modd;//记住modd和mod别用错了，n也要模一下,不然很难变成正的，求c^d的指数
		c=quick2(c,d%modd+modd,mod);//记住modd和mod别用错了，求c^d
		ll anss=(quick2(a,aaa,mod)*quick2(b,bbb,mod)%mod*quick2(c,ccc,mod))%mod;//记住modd和mod别用错了,求结果~~
		printf("%09lld\n",anss);//注意格式
	}
	return 0;
}