HZAU 1202 GCD （矩阵快速幂 + GCD）

HZAU 1202 GCD （矩阵快速幂 + GCD）

Problem Description

Xiao Ming found the compute time of gcd(fibn,fibn+1) is the most when he learnt the gcd, and the result of it is always fib1He wants to know what gcd(1+Sn,1+Sm)And gcd is greatest common divisor,fib1=1,fib2=1,fibn=fibn−1+fibn−2(n≥3) Sn=∑i=1nfibi

Input Description

The first line is an positive integer T. (1 ≤ T ≤ 10^3) indicates the number of test cases. In the next T lines, there are three positive integer n, m, p(1 ≤ n, m, p ≤ 10^9) at each line.

Output Description

In each test case, output the compute result of gcd(1+Sn,1+Sm)%p

Sample Input:

11 2 3

Sample Output:

1

题意

给出 n,m,p 三个整数，求斐波那契数列前 n 项和与前 m 项和的最大公约数模 p

思路

斐波那契数列有这样两条性质：

gcd(Fn,Fm)=Fgcd(n,m)

F1+F2+F3+F4+F5+...+Fn+1=Fn+2

于是，题目的答案便是 Fgcd(n,m)%p

最大公约数可以用辗转相除法求得，然后再利用矩阵快速幂得到斐波那契数第 k 项，记得模 p

AC 代码

#include #include #include #include using namespace std;typedef long long LL;LL n,m,mod;LL gcd(LL a,LL b){ if(b==0)return a; return gcd(b,a%b);}struct node{ LL mp[2][2]; void init(LL a,LL b,LL c,LL d) { mp[0][0]=a; mp[0][1]=b; mp[1][0]=c; mp[1][1]=d; } void mult(node x,node y) //两矩阵乘法 { memset(mp,0,sizeof(mp)); for(LL i=0; i<2; i++) for(LL j=0; j<2; j++) for(LL k=0; k<2; k++) mp[i][j]=(mp[i][j]+x.mp[i][k]*y.mp[k][j])%mod; };} init;struct node expo(struct node x, LL k) //进行k次幂运算{ struct node tmp; tmp.init(1,0,0,1); //单位矩阵 while(k) //快速幂部分 { if(k&1)tmp.mult(tmp,x); x.mult(x,x); k>>=1; } return tmp;}int main(){ int T; ios::sync_with_stdio(false); cin>>T; while(T--) { cin>>n>>m>>mod; int k=gcd(n+2,m+2); init.init(1,1,1,0); cout<

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。