HDU-4549(矩阵快速幂+欧拉定理)
题意：
F[0] = a, F[1] = b
F[n] = F[n-1] * F[n-2] (n > 1)现在给出a, b, n，你能求出F[n]的值吗？
思路：
将F[n]推到F[0], F[1]可发现F[n]能表示成两个连续斐波那契数次幂的F[0]和F[1]的乘积：F[n] = F[0]^(n-1)*F[1]^(n)。矩阵快速幂求出斐波那契数, 然后普通快速幂求出F[n]即可。
但会发现一个问题，假设k很大，x^k和x^(k%mod)是不等价的，所以求斐波那契数会很大存不下，也不能直接模mod。
需要利用下面的定理：
欧拉定理：x^ϕ(m) ≡ 1(mod m)
若m是素数，x为整数且无法被m整除，则就是费马小定理：x^(m-1) ≡ 1(mod m)。
则可得定理：
若a^b mod m 中b很大，则可转化为
a^b(mod m) = a^[b mod(m-1)](mod m);
证明如下：
令b = t*(m-1) + r; 其中t = b整除(m-1), r = b%(m-1);
则a^b = [a^(m-1)]^t * a^r (mod m);
= 1^t * a^r (mod m);
= a^r (mod m);
费马小定理的推广：如果p为质数，x^p-x（x是任意正整数）必能被p整除. (x^p-x = x*(x^(p-1) - 1);)
Code:
#include <bits/stdc++.h>
#define LL long long
using namespace std;
const LL mod = 1000000007;
struct node
{
LL a, b, c, d;
};
int a, b, n;
pair<LL, LL> pr;
node multi(node a, node b)
{
node ans;
ans.a = (a.a*b.a + a.b*b.c)%(mod-1);
ans.b = (a.a*b.b + a.b*b.d)%(mod-1);
ans.c = (a.c*b.a + a.d*b.c)%(mod-1);
ans.d = (a.c*b.b + a.d*b.d)%(mod-1);
return ans;
}
void quickM1(int b)
{
node ans, base;
ans.a = ans.d = 1; ans.b = ans.c = 0;
base.a = base.b = base.c = 1; base.d = 0;
while(b)
{
if(b&1) ans = multi(ans, base);
base = multi(base, base);
b >>= 1;
}
pr.first = ans.a, pr.second = ans.b;
}
LL quickM2(int a, LL b)
{
LL ans = 1, base = a;
while(b)
{
if(b&1) ans = ans*base%mod;
base = base*base%mod;
b >>= 1;
}
return ans;
}
int main()
{
ios::sync_with_stdio(0);
while(cin >> a >> b >> n)
{
if(n == 0) cout << a << endl;
else if(n == 1) cout << b << endl;
else
{
quickM1(n-1);
cout << quickM2(b, pr.first)*quickM2(a, pr.second)%mod << endl;
}
}
return 0;
}继续加油~
证明来自：http://www.cnblogs.com/cmyg/p/6647977.html