hdu5895-Mathematician QSC-2016沈阳网络赛-数学-各种奇怪姿势

题目链接

题意：数学题，给出几个递推式，求一个给出式，详情见题目链接

思路：
首先，补充几个姿势
1。降幂公式
2。不用逆元取模

对于f，已经给出了线性递推式，所以可以矩阵快速幂求出。
对于g,万能的队友们在oeis上找出了公式gn=f[n]*f[n+1]/2;
根据姿势1，最后的式子可以变形为
因为gn的求解过程中要除以2，2又不一定有逆元，所以要用上面的姿势2来得出指数，得出指数后普通快速幂就行了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
#include<stdio.h>
#include<string.h>
#include<math.h> 
using namespace std;
long long a[5][5];
long long e[5][5];
long long mod;
void mpp(long long n)
{   memset(a,0,sizeof(a));
    memset(e,0,sizeof(e));
	a[1][1]=2;
	a[1][2]=1;
	a[2][1]=1;
	a[2][2]=0;
    e[1][1]=1;
    e[2][2]=1;
    while(n>0)
    {   
    	if(n%2==1)
    	{
    		long long ans[4][4]={0};
    		for(int i=1;i<=2;i++)
    		 for(int j=1;j<=2;j++)
			  for(int k=1;k<=2;k++)
			 {
    		 	ans[i][j]=(ans[i][j]+(a[i][k]*e[k][j])%mod)%mod;
			 }
			for(int i=1;i<=2;i++)
			  for(int j=1;j<=2;j++)
			   e[i][j]=ans[i][j];   
		}
		long long ans[4][4]={0};
    	for(int i=1;i<=2;i++)
    	 for(int j=1;j<=2;j++)
		  for(int k=1;k<=2;k++)
			{
    		  ans[i][j]=(ans[i][j]+(a[i][k]*a[k][j])%mod)%mod;
			}
		n=n/2;
		for(int i=1;i<=2;i++)
			  for(int j=1;j<=2;j++)
			   a[i][j]=ans[i][j]; 
	}
}
long long phi(long long n)  
{     
    long long  i,cnt,j;  
    cnt=n;  
    for(i=2;i*i<=n;i++)  
    {  
      if(n%i==0)  
      {  
        cnt=cnt-cnt/i;  
        while(n%i==0)n=n/i;  
      }  
    }  
    if(n>1)cnt=cnt-cnt/n;  
    return cnt;  
      
}  
long long pp(long long a,long long n,long long mod)
{
	long long ans=1;
	while(n>0)
	{
		if(n%2==1)
		{
		  ans=ans*a%mod;
		}
		a=a*a%mod;
        n=n/2;
	}
	return ans;
}
int main()
{
	int i,j,k,t;
	long long n,y,x,s;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%lld%lld%lld%lld",&n,&y,&x,&s);
		n=n*y;
		mod=2*phi(s+1);
		mpp(n);
		long long phis=phi(s+1);
		long long fn=e[2][1];
		long long fn1=e[1][1];
		long long g=fn%mod*fn1%mod/2+phis;
		long long ans=pp(x,g,s+1)%(s+1);
		printf("%lld\n",ans);
	}
	return 0;
}