zoj 3547 – The Boss on Mars

这道题是这样的,给一个数列 a(n) = n^4,求所有与 n 互质的 k 的项 a(k) 的和。

这样考虑:

  1. 如果求 sum(k^4) {k=1..n},这个应该好办,可以求出公式,用 matlab 算一下:
syms k
symsum(k^4,1,k)

求得:

s(k) = sum = (k*(2*k + 1)*(k + 1)*(3*k^2 + 3*k - 1))/30

这个操作可以 O(1) 解决。

  1. 然后,我们求出所有 a(n) 的质因子,只要 k 里面含有这些因子,那些项就应该被删掉。然后我们可以枚举出所有质因数的组合,然后通过容斥原理求最终的结果。

例如,n = 2 * 2 * 3 * 5 * 7 = 420

求的的质因子为:[2, 3, 5, 7] 四个

  1. 初始化结果数为 ans = 0

然后我们枚举所有质因子组合,其乘积 mult 作为 n 的因子,共 2^4 个:

如果组合元素为偶数个,则在 ans 上加上 s(n/mult)*mult^4

如果组合元素为奇数个,则在 ans 上减去 s(n/mult)*mult^4

举例说明:

i) 枚举到空集时,因子为 1,应当在 ans 上加上:

= 1^4 + 2^4 + 3^4 + ... + 420^4
= s(420)
= 2629407815986

ii) 枚举到 [2] 时,因子为 2,应当在 ans 上减去:

= 2^4 + 4^4 + 6^4 + ... + 420^4
= (1^4 + 2^4 + ... + (420/2)^4) * 2^4
= s(210) * 16
= 1322520191888

iii) 枚举到 [3, 5] 时,因子为 15,应当在 ans 上加上:

= 15^4 + 30^4 + 45^4 + ... + 420^4
= (1^4 + 2^4 + ... + (420/15)^4) * 15^4
= s(28) * 50625
= 190183848750
# -*- coding: utf8 -*-
# 3493626 2013-12-21 19:59:09 Accepted 3547 Python 770 712 呆滞的慢板

# generate primes
b = [True]*10000
p = []
for i in range(2, 10000):
    if b[i]:
        p.append(i)
        for j in range(i*i, 10000, i):
            b[i] = False

# return prime factors of n
def f(n):
    ans = []
    for x in p:
        if n % x == 0:
            ans.append(x)
            while n % x == 0: n //= x
        if n == 1: return ans
    if n > 1: ans.append(n)
    return ans

# summary of k^4
M = 1000000007
def s(k): return (k*(2*k+1)*(k+1)*(3*k*k+3*k-1))/30 % M

# main
for t in range(int(raw_input())):

    n = int(raw_input())
    fact = f(n)

    ans = 0
    L = len(fact)
    for mask in range(1<<L):
        mult = sign = 1
        for i in range(L):
            if mask & (1<<i):
                mult *= fact[i]
                sign = -sign
        ans += sign*s(n//mult)*mult**4
        ans %= M

    print(ans)

【转载请附】愿以此功德,回向 >>

原文链接:http://www.huangwenchao.com.cn/2013/12/zoj3547.html【zoj 3547 – The Boss on Mars】

发表评论

电子邮件地址不会被公开。 必填项已用*标注