ProjectEuler 429 Sum of squares of uni - 拼圖

429. Sum of squares of unitary divisors

http://projecteuler.net/problem=429

如果一正整數n的因數d符合gcd(d, n/d) = 1，則稱d為n的「元因數」。

4! = 24的元因數共有1, 3, 8, 24四個，其平方和為1^2 + 3^2 + 8^2 + 24^2 = 650。

令S(n)為n的元因數的平方和，故S(4!) = 650。

請求出S(100000000!) mod 1000000009。

--