Abdelaleem's blog

By Abdelaleem, history, 7 weeks ago, In English

the problem ...

https://codeforces.com/group/H10hR2t6Sj/contest/338701/problem/J

Let M be a positive integer.

Let f(M) be the number of positive divisors of an integer M.

For example f(12)=6 and they are 1,2,3,4,6,12.

Let g(M) be The summation of number of divisors of the divisors of an integer M.

Mathematically we can say g(M)=∑i|Mf(i), where | means divides.

For example, g(12)=f(1)+f(2)+f(3)+f(4)+f(6)+f(12)=1+2+2+3+4+6=18.

You are given an integer n, Calculate g(n!).

* While ..( 1 ≤ n ≤ 1e6 ).*****

How i can solve this Problem ?

 
 
 
 
  • Vote: I like it
  • +8
  • Vote: I do not like it

»
7 weeks ago, # |
Rev. 4   Vote: I like it -12 Vote: I do not like it

.

»
7 weeks ago, # |
  Vote: I like it +15 Vote: I do not like it
  • The number of divisors for some number $$$n$$$ with prime factorization $$$p_1^{a_1}p_2^{a_2} \dots p_k^{a_k}$$$ is $$$(a_1 + 1)(a_2 + 1) \dots (a_k + 1)$$$.
  • You can try to find the value of the function $$$g$$$ for some number $$$n$$$ with a simple prime factorization $$$p^a$$$: $$$g(p^a) = \sum_{x=0}^{a} (x+1) = \frac{(a+1)(a+2)}{2}$$$.
  • Then you can try to find the value of the function $$$g$$$ for some number $$$n$$$ with a bit more complex prime factorization $$$p^aq^b$$$: $$$g(p^aq^b) = \sum_{x=0}^{a}\sum_{y=0}^{b} (x+1)(y+1) = \big( \sum_{x=0}^{a} (x+1) \big) \big( \sum_{y=0}^{b} (y+1) \big) = \frac{(a+1)(a+2)}{2}\frac{(b+1)(b+2)}{2}$$$.
  • And so on. You can easily see that the function $$$g$$$ is multiplicative.
  • So the problem is reduced to the prime factorization of $$$n!$$$ which can be done by several ways (note that the limit for $$$n$$$ is small enough).
»
7 weeks ago, # |
Rev. 2   Vote: I like it +6 Vote: I do not like it

First we have to calculate f(i) for all 1<=i<=n;

We can do this in nlog(n) time;

f(i)

Now g(n!) means f(1)+f(2)+f(3)+....f(n), because 1-n all are divisors of n!.

so just calculate the prefix sum of f(i).

Presum

Now answer all the queries in O(1)

Full code
  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    What about all the divisors of n! that are more than n?

    • »
      »
      »
      7 weeks ago, # ^ |
        Vote: I like it +39 Vote: I do not like it

      Ah! My bad. That's why I always get a WA on pretest 2. ༎ຶ‿༎ຶ

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

First find prime factorization of all number upto n to find the contribution of each prime in n!. This can be done $$$nlog(n)$$$ using sieve [maintaining spf].

Let our $$$val$$$ array contains the contribution of each prime.

we can calculate the answer upto i as

val[i]=(val[i-1]+val[i-1]*(((val[i]+1)*(val[i]+2))/2-1)+((val[i]+1)*(val[i]+2))/2-1);

As if prime p has contribution a, it will contribute to the answer as $$$div(p)+div(p2)+div(p^3)...+div(p^a)$$$ which is $$$2+3+...+(a+1)$$$ note that we are exculding 1 here to prevent double counting, we will add 1 at the end. Finally the final answer is $$$val[n]+1$$$

»
7 weeks ago, # |
Rev. 3   Vote: I like it +6 Vote: I do not like it

the problem is to find number of pairs $$$ (x , y) $$$ such that $$$ x | y | n! $$$

let $$$ n! = {p_1}^{a_1} . {p_2}^{a_2} \dots {p_k}^{a_k}$$$ , $$$ x = {p_1}^{b_1} . {p_2}^{b_2} \dots {p_k}^{b_k}$$$ and $$$ y = {p_1}^{c_1} . {p_2}^{c_2} \dots {p_k}^{c_k}$$$.

now because $$$ x | y | n! $$$ , for every $$$ i $$$ , $$$ {b_i} <= {c_i} <= {a_i} $$$ should be held.

so for each $$$ i $$$ you need to find number of pairs $$$ ({b_i} , {c_i}) $$$ such that $$$ 0 <= {b_i} <= {c_i} <= {a_i} $$$. and it's easy to see that there are $$$ \dfrac{({a_i + 1}).({a_i + 2})}{2} $$$ such pairs.

and the final answer is $$$ \dfrac{({a_1 + 1}).({a_1 + 2})}{2} . \dfrac{({a_2 + 1}).({a_2 + 2})}{2} . \dots \dfrac{({a_k + 1}).({a_k + 2})}{2} $$$ .

UPD : $$$ x | y $$$ denotes that y is divisible by x.

  • »
    »
    7 weeks ago, # ^ |
    Rev. 2   Vote: I like it -11 Vote: I do not like it

    What does “stick” denote in x|y|n! ? Does it means n % y == 0 && y % x == 0?

    • »
      »
      »
      7 weeks ago, # ^ |
        Vote: I like it +14 Vote: I do not like it

      time needed to write a comment > time needed to search in Google.

  • »
    »
    7 weeks ago, # ^ |
    Rev. 3   Vote: I like it +1 Vote: I do not like it

    Ah, got it: y here is every divisor of n! that goes into f(…) in this formula g(z) = f(div1) + … + f(div.m) and number of x’s is value of f(y) by f() defenition. Nice!

    • »
      »
      »
      7 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you plz write its code and share it. I am unable to understand the approach

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Abdelaleem (previous revision, new revision, compare).