?
?
题意非常简单，
a,b,n
都是正整数，求
Sn=?(a+b√)n?%m,(a?1)2
这个题目也是2008年Google Codejam Round 1A的C题。
做法其实非常简单，记
(a+b√)n
为
An
，配项
Cn=An+Bn=(a+b√)n+(a?b√)n
两项恰好共轭，所以
Cn
是整数。又根据限制条件
(a?1)2
也就是说
Cn=?An?
Sn=(Cn)%m
求
Cn
的方法是递推。 对
Cn
乘以
(a+b√)+(a?b√)
于是
Cn+1=2aCn?(a2?b)Cn?1
把这个递推式写成矩阵形式
[Cn+1Cn]=[2a1?(a2?b)0][CnCn?1]
于是就可以用矩阵快速幂来做了
[Cn+1Cn]=[2a1?(a2?b)0]n[C1C0]
---------------------------------------------------------------------------- 以上是原版的题解。 这个题目是我做训练赛的时候做到的，当时没做出来，后来看题解，一开始不明白为什么C[N]=[ A[N] ]; 后来的时候百度了一下共轭的定义发现： C[N]一定是一个整数。 B[N]又小于1. 所以 C[N]=[ A[N] ]=A[N]+B[N];
#include
#include
#include
#include
#include
#include
#include
#include