hdu 3221 Brute-force Algorithm (矩阵快速幂+指数循环节)

题目链接

 

题意:给出了一段伪代码。分析得知其实就是f[1]= a,f[2] = b,f[n]=f[n-1] * f[n-2]

思路:一眼题,和hdu4549很类似hdu4549解题报告

不同的是这道题中p不一定是质数(其实不是也无所谓啊…hdu4549只不过是因为1E9+7是指数,又用费马小定理化简了一下,这道理%phi(p)即可)

还有这道题让我知道了

首先我们知道指数循环节公式,也就是所谓的降幂公式为:a^x = a^(x mod phi(c)+phi(c)) (mod c) x>=phi(c),(ps:后面的限制条件,在x<phi(c)的时候,该式子依然正确,只不过增加了运算复杂度。。。? 存疑)

括号里的话是错误的。只有当x<phi(c)的时候,这个公式才成立。

这道题就是反例,不加判断会wa。

 

 

 

作者: CrazyKK

ex-ACMer@hust,researcher@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz