欧拉项目 | 123题 | 质数平方余数

$p_n$表示第$n$个质数，$r$是$(p_n-1)^n+(p_n+1)^n$模$p_n^2$的余数。
求满足余数$r$超过$10^{10}$的$n$的最小值。

这道题相对比较简单，问题的关键在于找到一个简单的方式来表达$r$。我们先把$(p_n-1)^n$展开看看。
$$(p_n-1)^n=\binom{n}{n}p_n^n+\binom{n}{n-1}(-1)^1p_n^{n-1}+\cdots+\binom{n}{2}(-1)^{n-2}p_n^2+\binom{n}{1}(-1)^{n-1}p_n+\binom{n}{0}(-1)^n$$
除了最后两项，其他能被$p_n^2$整除。$(p_n+1)^n$类似。
所以
$$r=n(-1)^{n-1}p_n+(-1)^n+n(1)^{n-1}p_n+(1)^n$$
$n$为偶数时
$$r=n(-1)p_n+1+n(1)p_n+1=2$$
显然不大于$10^{10}$
$n$为奇数时
$$r=np_n-1+np_n+1=2np_n$$
我们只需要考察$n$是奇数即可，同时，给定$n$，我们能够很快的计算出$r$的值。

写代码得到答案。

var primes = Utils.GenPrimes(1000000).Where(p => p != 0).ToList();
int n = 7039;
for (; n < primes.Count; n += 2)
{
    var r = 2 * n * primes[n - 1];
    if (r > 10000000000)
    {
        break;
    }
}

这里说明两个事情：

7037是题目给出的数，其对应的$r$第一次超过了$10^9$，所以我们从7039开始找即可；其实多算7000多个数也消耗不了啥时间；
primes[n - 1]减一的原因是数组从0开始，而不是1。