Ipad,IPhone

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 285    Accepted Submission(s): 100

In ACM_DIY, there is one master called “Lost”. As we know he is a “-2Dai”, which means he has a lot of money.
  


Well, Lost use Ipad and IPhone to reward the ones who solve the following problem.
  


In this problem, we define F( n ) as :
  


Then Lost denote a function G(a,b,n,p) as


Here a, b, n, p are all positive integer!
If you could tell Lost the value of G(a,b,n,p) , then you will get one Ipad and one IPhone!

4
2 3 1 10007
2 3 2 10007
2 3 3 10007
2 3 4 10007

40
392
3880
9941

第二个：参考http://blog.csdn.net/u010690055/article/details/9271547

/*
HDOJ 3802 数论 矩阵乘法等 

数论完全小白，参考别人的。 
根据欧拉准则，即二次剩余的欧拉判别法 ，
我们知道a是模p的二次剩余时a^((p-1)/2)=1(mod p)，
非二次剩余时，a^((p-1)/2)=-1(mod p) ，
所以二次剩余时，前半部分的解为4，而非二次剩余的时候，前面的解为0，

构造矩阵：
见上图：十分详细 
*/
#include<iostream>
#include<stdio.h>
using namespace std;
typedef __int64 LL; 
struct matrix{
	LL map[2][2];
};
LL p,a,b,n; 

matrix multi(matrix A,matrix B)  
{  
    matrix ans;  
    for(int i=0;i<2;i++)  
        for(int j=0;j<2;j++)  
        {  
            ans.map[i][j]=0;  
            for(int k=0;k<2;k++)  
                ans.map[i][j]=(ans.map[i][j]+A.map[i][k]*B.map[k][j])%p;  
        }  
    return ans;  
}  

matrix powMatrix(matrix x,LL n)  
{  
    matrix ans; 
    int i,j;
	for(i=0;i<2;i++)
  		for(j=0;j<2;j++)
  		{
	   		if(i==j)
	    		ans.map[i][j] = 1;
	   		else
	    		ans.map[i][j] = 0;
	  	} 
	for(;n;n>>=1)
 	{
    	if(n&1)
    		ans=multi(ans,x);
    	x=multi(x,x);
	}
    return ans;  
} 
 
LL powNum(LL x,LL n)
{
	LL ans=1;
	for(;n;n>>=1)
	{
		if(n&1)
			ans=(ans*x)%p;
		x=(x*x)%p;
	} 
	return ans;
}

int main()
{
	int t;
	LL power,aa,bb,keep3,result;
	matrix res;
	
	//freopen("test.txt","r",stdin);
	scanf("%d",&t);
	while(t--)
	{
		scanf("%I64d%I64d%I64d%I64d",&a,&b,&n,&p);
		LL aa=(1+powNum(a,(p-1)/2))%p;
		LL bb=(1+powNum(b,(p-1)/2))%p;
		if(n==0)
			power=1;
		else
		{
			res.map[0][0] = 1;
    		res.map[0][1] = 1;
    		res.map[1][0] = 1;
    		res.map[1][1] = 0;
    		p--;
			res=powMatrix(res,n-1);
			p++;
			power=(res.map[0][0]+res.map[0][1])%(p-1);	
		}
		
		power+=p-1;
        res.map[0][0] = (a+b)%p;
  		res.map[0][1] = (2*a*b)%p;
  		res.map[1][0] = 2%p;
  		res.map[1][1] = (a+b)%p;
  		res=powMatrix(res,power-1);
  		keep3=(2*(((res.map[0][0]*(a+b))%p+(res.map[0][1]*2)%p)%p))%p;
        
		result = 1;
  		result = (result*aa)%p;
        result = (result*bb)%p;
  		result = (result*keep3)%p;
  		printf("%I64d\n",result); 
	}
	return 0;
}