一点一点前进...

0%

欧拉项目 | 500题 | 因数个数问题

发表于 分类于 ， Disqus：

这是欧拉项目的第五百个题目，原题链接

题目描述很简单，120个有16个因数，是最小的拥有16个因数的数字。求最小有2 ^ 500500个因数的数字，因为这个值相当大，要求给出模500500507的结果。

首先，我们要明白，如何求一个数有多少个因数？
这里需要用到Euler’s totient function，这里不得不提一句，出题人很用心，第500题，一个有里程碑意义的题目，需要用到Euler本人的研究成果。

根据这个定理，把前500500个质数相乘，那个数字就有2的500500次方个因数。但是肯定不是最小的，因为当前2出现了一次，对因数的个数贡献是2的1次方，那么再乘以2个2，2的次数是3次，对因数的贡献是2的平方，那么不用乘以第500500个质数，就能使得因数个数是2的500500次方，显然后面比较小，这是第一个数字乘以第500500个质数，再除以4。要让2的贡献再过一次方，达到2的3次方，那么需要再多4个2，使得有7个2，显然4个2比第500504个质数小很多。就这样子继续下去。然后继续考虑3、5、7等等。

Wolfram Alpha理论会告诉我们一些关于质数次方的定理，能够知道每个质数都出现多少次，贡献多少个2的次方。

大致思路如下，具体的看代码吧。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
const long mod = 500500507;
long answer = 1;
var primes = Utils.GenPrimes(8000000).ToList();

for (int i = 0; i < 500084; i++)
{
	answer *= primes[i];
	answer %= mod;
}

for (int i = 0; i < 396; i++)
{
	answer *= (long)Utils.Pow((int)primes[i], 2);
	answer %= mod;

}

for (int i = 0; i < 15; i++)
{
	answer *= (long)Utils.Pow((int)primes[i], 4);
	answer %= mod;
}

for (int i = 0; i < 4; i++)
{
	answer *= (long)Utils.Pow((int)primes[i], 8);
	answer %= mod;
}

answer *= (long)Utils.Pow((int)primes[0], 16);

return answer % mod;