一点一点前进...

0%

欧拉项目 | 题目120 | 求(a-1)^n + (a+1)^n除以a^2的最大余数

发表于 分类于 ， Disqus：

题目链接

给定一个a，n取何值时能让(a-1)^n + (a+1)^n % a^2最大呢？
首先考虑n是偶数的时候，
(a-1)^n + (a+1)^n
= 2 * (a^n + Cn,2*a^(n-2) + Cn,4*a^(n-4) + … + 1)
由于n是偶数，a^n能够被a^2整除，同理，a^(n-2)，a^(n-4)…a^2都可以被a^2整除。
所以，最后的余数是1，显然不大，下面我们考虑n是奇数的时候。
(a-1)^n + (a+1)^n
= 2 * (a^n + Cn,2*a^(n-2) + Cn,4*a^(n-4) + … + Cn,n-1*a)
a^n模a^2余数是a，同理，a^(n-2)…a模a^2都余a。
那么上面的数模a^2等于
2*a*(1+Cn,2+Cn,4+…+Cn,n-1) = 2*a*f(n)

想要2*a*f(n)模a^2余数最大呢，让2*a*f(n)越接近a^2越好，也就是2*f(n)越接近a越好，但是不能等于a。
2*f(n)一定是偶数。所以，当a是奇数的时候，2*f(n)=a-1，当a是偶数的时候，2*f(n)=a-2。

有了以上的分析，很容易就能写出获取Rmax的函数：

1
2
3
4
private static int GetMaxRByA(int a)
{
	return (a - 1) / 2 * 2 * a;
}

离最后的答案只差一步：

1
2
3
4
5
6
7
8
9
10
11
public static int GetAnswer()
{
	List<int> rs = new List<int>();

	for (int a = 3; a <= 1000; a++)
	{
		rs.Add(GetMaxRByA(a));
	}

	return rs.Sum();
}

有了数学分析得到的结论之后，程序的时间复杂度是O(n)，理论最低值了，而且这里n就1000，在我的机器上，14ms就完成了。