var
n:longint;
function g(k:longint):longint;
begin
if k<=1 then g:=k
else g:=(2002*g(k-1)+2003*g(k-2)) mod 2005;
end;
begin
read(n);
write(g(n));
readln;
end.
从前向后，算算
q[0]=q[1]=1,q[2]=0; q[3]=2002,q[4]=2002*2003 mod 2005.....
容易求出g:=2002*g(k-1)+2003*g(k-2) 的通项公式（用特殊根法就可以，不知道的看组合数学教科书），然后做一些数学变形有logN的方法求g[n] mod 2005的值，我就是这么做的，想不出更好的方法。
1) 求出通项 g[n]=n*2005+(-1)^(n-1)*(2^n-1)
得出g[2005]=n*2005+2^2005-1
2)由费马小定理,得出 g[2005]=k*401+2^5-1=31
(附:费马小定理,若r是一个质数,则p^r-p能被r整除)
3)判断:g[2005]=k*5+1 (这一部普通推倒就可,实在不行列举前几个,马上就能找到规律)
4)根据中国剩余定理,得出g[2005]=k*2005+31
5)填 31
{k是一个参数,不表示一个定值,无实际意义,这里我不会打同余号,只好这样代替一下}
由递推式：f(n)=2002f(n-1)+2003f(n-2)
f(0)=0,f(1)=1
利用特征方程解出通项式：f(n)=(2003^n-(-1)^n)/2004
再求f(n) mod 2005的结果，下面的解法同4楼
答案是31,化为f[n]=(2^n-1) mod 2005 (n=2k+1)
=(2006-2^n) mod 2005 (n=2k)
(2^2005-1) mod 2005=31(数学方法)
当时算到最后一步算不出,考后请教数学竞赛的同学算出31
用什么欧拉质数定理: a^f[a] mod m=1
(a与m互质)
a=p1^a1*p2^a2......pn^an(p1,p2...pn为质数)
f[a]=p1^[a1-1]*p2^[a2-1]....pn[an-1]*[p1-1]*[p2-1]...[pn-1]
算出2^400 mod 401=1
2^4 mod 5=1 => 2^400 mod 5=1(这一步用2^4=5k+1,2^400=(2^4)^100=(5k+1)^100=5^100*k^100+....C(n,n-1)*5k+C(n,n) 除5余数为1证明)
进而2^400 mod 2005=1
2^2000 mod 2005=1
2^2005 mod 2005=2^5=32
..
网上查的
