一点一点前进...

0%

欧拉项目 | 429题 | 元因数的平方和

发表于 分类于 ， Disqus：

429题链接

整数n的元因数（unitary divisor）d满足gcd(d, n/d) = 1
4! = 24的元因数有1，3，8，24
它们的平方和是1^2 + 3^2 + 8^2 + 24^2 = 650

S(n)表示n的元因数的平方和
求S(100 000 000!)模1 000 000 009

将n分解质因数，可以写作
n = p1^k1 + p2^k2 + ... + pm^km
那么元因数就是完全占有某些质数，比如p1^k1和p2^k2 + ... + pm^km就是一对元因数
有多少元因数呢？2^m个，一个很典型的排列组合问题。
我们下面看看平方和有什么规律。先看几个简单的。
将pi^ki记作qi
有两个质因数，那么平方和

1
2
S = 1 + q1^2 + q2^2 + (q1q2)^2
  = (1+q1^2)(1+q2^2)

有三个质因数呢？

1
2
S = 1 + q1^2 + q2^2 + q3^2 + (q1q2)^2 + (q1q3)^2 + (q2q3)^2 + (q1q2q3)^2 
  = (1+q1^2)(1+q2^2)(1+q3^2)

我在纸上推理了四个质因数的情况，进而猜测到S = (1+q1^2)(1+q2^2)...(1+qm^2)
更通用的公式在这里

假定我们已经有了质因数的分解，那么很容易就能求出平方和了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
long m = 1000000009;
long ret = 1;
foreach (var pair in factors)
{
    var p = pair.Key;
    var k = pair.Value * 2;
    long r = 1;
    for (int i = 0; i < k; i++)
    {
        r *= p;
        r %= m;
    }
    ret *= (r + 1);
    ret %= m;
}

return ret;

现在的问题是如何得到100 000 000!的质因数，我们需要知道有多少个2，多少个3，多少个5等等。
Legendre’s formula给出了n!分解质因数的方法，这个方法简单易懂。
得到小于100 000 000的所有质数（筛选法），然后循环计算指数就可以了。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
var factors = new Dictionary<long, int>();
foreach (var p in primes)
{
    if (p != 0)
    {
        int i = 1;
        int power = 0;
        while (true)
        {
            var cur = n / (long)Math.Pow(p, i);
            if (cur == 0)
            {
                break;
            }

            power += (int)cur;
            i++;
        }

        factors[p] = power;
    }
}