一个高中的信息学竞赛的题
#include <stdio.h>
long g(long k) {
if (k <= 1) return k;
return (2002 * g(k - 1) + 2003 * g(k - 2)) % 2005;
}
int main() {
long n;
scanf( "%ld ", &n);
printf( "%ld\n ", g(n));
return 0;
}
输入：2005
输出：
[解决办法]
可以转换成
g(0)=0
g(1)=1
g(n)=2002g(n-1)+2003g(n-2) (n> 1) ..........[1]
求g(2005)%2005
对于[1] 可以求到通项公式：
求解如下，
x^2-2002x-2003=0
得到 x1=20003 x2=-1
所以 通项为 (2005-2)^(n-k0) +(-1)^(n-k0)
再根据g(0),g(1)的值应当可以得到 k0的值得
到这时 问题差不多已经解决了
[解决办法]
看来楼主想得到一个分析解.让我们试着用一点初等数论的知识解决此题.
首先,让我们试着求出g(k)的通项公式.
令数列f(k)满足
f(0)=0, f(1)=1, f(k)=2002*f(k-1) + 2003*f(k-2)
则有 g(k) = f(k) % 2005
(注意同余式的基本性质: 若M=m(mod 25), N=n(mod 2005), 则对任意整数a,b,有 a*M+b*N = a*m+b*n (mod 2005) )
f(k)是个齐次递归数列,其通项公式(如12楼zhulinpptor指出的)由特征方程
x^2-2002x-2003=0 决定
因为方程有两个根 x1=2003, x2=-1, f(k)的通项公式为
f(k) = m*2003^k + n*(-1)^k
其中m,n为待定系数
由f(0)=1, f(1)=1 不难得出 m=1/2004 n=-1/2004
故有
f(k) = 1/2004*2003^k - 1/2004*(-1)^k
= 1/2004 * ((2003)^k - (-1)^k)
从而
g(k) = f(k) % 2005
= (1/2004 * ((2003)^k - (-1)^k)) % 2005
= (-1 * ( (-2)^k - (-1)^k)) % 2005 // 注意 1/2004=1/-1=-1 (mod 2005), 2003=-2 (mod 2005)
= (-1 * (-1)^k * (2^k - 1)) % 2005
即 g(k) = ((-1)^(k+1) * (2^k - 1)) % 2005
上式就是g(k)的通项公式
因此, g(2005) = ((-1)^2006 * (2^2005 - 1)) % 2005
= (2^2005 - 1) % 2005
现在的问题是,如何计算2^2005这样大的一个数除以2005的余数? 如果我们能找到某个数n,使得
2^n = 1 (mod 2005), 那我们只需计算2的(2005%n)次幂就行了,大大减小计算量.
学过数论的同学马上就会想到Euler定理
2005只有两个素因子 5, 401, 因此它的Euler数是
(5-1)*(401-1) = 1600
故有 2^1600 = 1 (mod 2005)
简单的计算我们还可得到比上式更该的结果,实际上,有
2^200 = 1 (mod 2005)
有了上式这个工具,g(2005)就呼之欲出了:
g(2005) = (2^2005 -1) % 2005
= (2^2000*2^5 -1 ) % 2005
= (2^5 -1 ) % 2005
= (32 - 1) % 2005
= 31
