不得不说，读懂题就花了不少时间……
最后发现它说了这么多就是为了解释它让我们求的式子的来源……
· 题目
对于数列 $A=(a_0,a_1,a_2,…)$ ，定义：
对于实数 $c$，我们根据它定义数列：
给定正整数 $A,B,n$ ；根据 $A$ 构造数列 $U_A$（记 $U_A$ 中的元素为 $u_i$），根据 $B$ 构造数列 $E_\sqrt{B}$（记 $E_\sqrt B$ 中的元素为 $e_i$）；求：
输出时，第一行输出 $q$，接下来 $q$ 行，每行输出整数 $a_i,b_i$；表示答案为 $\sum_{i=1}^qa^i\sqrt {b_i}$。
· 解析
根据题目我们可以知道：
那么可以知道：
因为对于任何实数 $x$ ，满足：
所以我们可以得到（理解一下，可能需要思考~）：
再继续推导：
把上面这个式子先留着（上面的这个式子是我们要求的答案）；我们先来看另一个式子的推导：
$(a+b\sqrt t)(c+d\sqrt t)=(ac+bdt)+(ad+bc)\sqrt t$ （$a,b,c,d,t$ 均为常数）
知道这个等式有什么用呢？
可以发现形如 $(a+b\sqrt t)$ 的两个式子相乘，我们仍可以得到一个形如 $(a+b\sqrt t)$ 的式子，于是…… $(A+\sqrt B)^n$ 和 $(A-\sqrt B)^n$ 展开后也会得到形如 $(a+b\sqrt t)$ 的式子。
多项式的幂？式子的形式相同？——快速幂
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| ll SQPow(ll fir,ll sec,ll thi,ll B,ll mod){
ll resfir=1,ressec=0;
while(thi){
if(thi&1){
ll _resfir,_ressec;
_resfir=(resfir*fir%mod+ressec*sec%mod*B%mod)%mod;
_ressec=(ressec*fir%mod+resfir*sec%mod)%mod;
resfir=_resfir;ressec=_ressec;
}
ll _fir,_sec;
_fir=(sec*sec%mod*B%mod+fir*fir%mod)%mod;
_sec=fir*sec%mod*2%mod;
fir=_fir;sec=_sec;
thi>>=1;
}
return ressec;
}
|
令 $(A+\sqrt B)^n=P_1+Q_1\sqrt B, (A-\sqrt B)=P_2+Q_2\sqrt Ｂ$ （$P_1,P_2,Q_1,Q_2$是常数）；
可以发现 $P_1=P_2=A^n+A^{n-2}B+A^{n-4}B^2…$ ，所以 $(A+\sqrt B)^n-(A-\sqrt B)^n=(Q_1-Q_2)\sqrt B$ ；那么答案就是：
可见要将上式表示为 $\sum_{i=1}^qa_i\sqrt {b_i}$ 的形式 —— 令 $B=x^2y(x是尽可能大的正整数)$，则 $q=1,a_1=(Q_1-Q_2)x,b_1=y$ 。（别忘了分解质因数）
· 源代码
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
|
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
ll A,B,n,P;
int prm[1005],nprm;
bool vis[1005];
ll SQPow(ll fir,ll sec,ll thi,ll B,ll mod){
ll resfir=1,ressec=0;
while(thi){
if(thi&1){
ll _resfir,_ressec;
_resfir=(resfir*fir%mod+ressec*sec%mod*B%mod)%mod;
_ressec=(ressec*fir%mod+resfir*sec%mod)%mod;
resfir=_resfir;ressec=_ressec;
}
ll _fir,_sec;
_fir=(sec*sec%mod*B%mod+fir*fir%mod)%mod;
_sec=fir*sec%mod*2%mod;
fir=_fir;sec=_sec;
thi>>=1;
}
return ressec;
}
ll QPow(ll under,ll over,ll mod){
ll res=1;
while(over){
if(over&1) res=res*under%mod;
under=under*under%mod;
over>>=1;
}
return res;
}
ll Primnum(ll num){
ll ret=1;
for(int i=1;i<=nprm;i++){
int cnt=1;
while(num%prm[i]==0){
num/=prm[i];
cnt++;
if(cnt&1) ret*=prm[i];
}
}
return ret;
}
void Process(){
int lim=1000;
for(int i=2;i<=lim;i++){
if(!vis[i]) prm[++nprm]=i;
for(int j=1;i*prm[j]<=lim && j<=nprm;j++){
vis[i*prm[j]]=true;
if(i%prm[j]==0) break;
}
}
}
int main(){
Process();
int ncase;scanf("%d",&ncase);
while(ncase--){
scanf("%lld%lld%lld%lld",&A,&B,&n,&P);
ll res1=SQPow(A,1,n,B,P*2),res2=SQPow(A,-1,n,B,P*2);
ll prtsec,delta=Primnum(B);
prtsec=(res1-res2+P*2)%(P*2)/2;
prtsec=prtsec*delta%P;
B=B/delta/delta;
printf("1 %lld %lld\n",prtsec,B);
}
return 0;
}
|
The End
Thanks for reading!
Email: lucky_glass@foxmail.com ，欢迎提问~