Tuesday, August 9, 2011
Divisors problem (one more)
Here is a problem w.r.t divisors: For a given positive integers B and X find the number of positive integers N such that number N*X has at least one divisor D such that N < D <= B (Courtesy: www.codechef.com).
The number N, can be represented as a function of B and X, namely f(B, X). Prove the following:
f(B, 1) = 0
f(B, 2) = Floor(B / 2)
f(B, 3) = 2 * Floor(B / 3) - Floor(B / 6)
f(B, 4) = Floor(B / 2) + Floor(B / 4) - Floor(B / 6)
f(B, 5) = 4 * Floor(B / 5) - Floor(B / 10) - Floor((B + Floor(B / 15)) / 8) - Floor((B + Floor(B / 20)) / 7)
The number N, can be represented as a function of B and X, namely f(B, X). Prove the following:
f(B, 1) = 0
f(B, 2) = Floor(B / 2)
f(B, 3) = 2 * Floor(B / 3) - Floor(B / 6)
f(B, 4) = Floor(B / 2) + Floor(B / 4) - Floor(B / 6)
f(B, 5) = 4 * Floor(B / 5) - Floor(B / 10) - Floor((B + Floor(B / 15)) / 8) - Floor((B + Floor(B / 20)) / 7)
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment