某程序阅读题

Description

一道程序阅读题。如下（稍作修改）：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n;
int g(int k){
    if(k<=1) return k;
    return (2002*g(k-1)+2003*g(k-2))%2005;
}
signed main(){
    scanf("%lld",&n);
    printf("%lld
",g(n));
    return 0;
}

输入：(2005)。求输出。

Solution

Part 1

首先，可以转化为 (g(x)=(-3g(x-1)-2g(x-2))\%2005)。我们要找到 (f(x)=-3g(x-1)-2g(x-2)) 的通项公式。

通过列举来找规律：(f(1)=1,f(2)=-3f(1)-2f(0)=-3,f(3)=-3f(2)-2f(1)=9-2=7,f(4)=-15cdots)

发现 (f(1)=2^1-1,f(2)=-(2^2-1),f(3)=2^3-1,f(4)=-(2^4-1)cdots)

通项公式：(f(x)=(-1)^{x-1}(2^x-1))。

答案应该是：(g(2005)=(-1)^{2004} imes (2^{2005}-1)\%2005)
(=(2^{2005}-1)\% 2005=2^{401 imes 5}\% 2005-1)
(=(2^{401} imes 2^{401} imes 2^{401} imes 2^{401} imes 2^{401})\% 2005-1)

Part 2

费马小定理：若 (m) 为质数，且 (gcd(a,m)=1)，则 (a^{m−1}equiv 1pmod m)。

由于 (401) 是质数，且 (gcd(2,401)=1)，所以 (2^{401-1}equiv 1pmod {401})。

(2) 和 (401) 互质，因为 (5) 和 (2) 互质，所以：

(g(2005)=(2^{401} imes 2^{401} imes 2^{401} imes 2^{401} imes 2^{401})\% 2005-1)
(=(2 imes 2 imes 2 imes 2 imes 2)\% 2005-1)
(=31)

Part 3

这是计算 (g(2005)=(2^{2005}-1)\% 2005=2^{401 imes 5}\% 2005-1) 的另一种方法。

(2^4mod 5=1)，所以 (2^{400}mod 5=1)，(2^{401}mod 5=2)。

(2^{401-1}equiv 1pmod {401})，即 (2^{401-1}mod 401=1)，所以 (2^{401}mod 401=2)。

又因为 ( ext{lcm}(5,401)=2005,2^{401}mod 2005=2)，所以 (2^{2005}mod 2005-1=2^5-1=31)。

答案： (31)。