hdu 4794 Arnold (二次剩余,斐波那契循环节)

题意:

给定一个 NN(N4e9) 的矩阵,现在经过这样一个变换:将 (x,y) 变为 ((x+y)%N,(x+2×y)%N)(0x<N,0y<N) 现在求经过多少次这样的变换之后在回到 NN 的原始矩阵。

思路:

在模n的剩余系下可以写成(fib(n)x+fib(n+1)y,fib(n+1)x+fib(n+2)y)的形式fib(n)表示Fibonacci数列的第n项

所以就成了斐波那契数列循环节。。经典题。注意会爆long long,要用ULL

又写了遍板子,去年的东西都忘得差不多了orz

 

 

作者: CrazyKK

ex-ACMer@hust,researcher@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz