minhduc viết:
QUOTE:
Yes, the above method is correct.
An artihmetic function f(n) that satisfies f(mn) = f(m)f(n) for (m,n)=1 is called a multiplicative function. For any multiplicative function f that has an easy way to compute f(p^k), you could compute f[1..n] in O(nloglogn) using the sieve of Erasthosenes.
Yeah, multiplicative functions are interesting!
QUOTE:
Hint: how to compute (n div 1) + (n div 2) + ... + (n div n) in O(logn)?
I find that complicated
For example n = 10: computing S = sum(n div d) | d = 1,2,...,n
| Code: |
d: 1 2 3 4 5 6 7 8 9 10
n/d: 10 5 3 2 2 1 1 1 1 1 (*)
|
Here, how to group the terms (in (*)) that share the same value of n/d?
Được ưa thích: 2
