uva 10655 – Contemplation! Algebra (构造矩阵,快速幂)

uva10655题目链接

题意:

给出a+b和ab的值,问a^n+b^n

思路:

构造矩阵,手写一下很显然…

转移矩阵M=[0 , 1]

[-q,p ]

初始矩阵M1=[p           ]

[p^2-2*q]

快速幂即可。

有个坑点在于..读入的结束是p=0&q=0,并且只有这两个输入。

如果用p=0&&q=0作为终止条件,那么就会将三个输入,但p==0&&q==0的情况错误得终止…

正确的做法是 while (~scanf(“%lld%lld%lld”,&p,&q,&n)==3)

 

 

 

作者: CrazyKK

ex-ACMer@hust,researcher@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz