vasandani68's blog

By vasandani68, history, 3 years ago, In English,

Can anyone provide an explanation for this problem!! I am not able to understand the basic idea.

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

it simply search the result based on formula, for example, for n = 2

the result = 2/gcd(1,2) + 2/gcd(2,2) = 2 + 1 = 3

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It is a naive approach and will time out.Please re-read the constraints and answer accordingly.

»
3 years ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

the sum =

where d is a divisor of n and φ(x) is euler's totient function ... I don't have a proof for it ,I thought it was symmetric to which is equal to (from oeis) and it worked

you can precompute φ in O(n log n) after sieve

and you can generate all divisors of a number in O(number of divisors) using the information generated by sieve

then you can evaluate this sum in O(number of divisors) ... I don't know if that is enough to pass the TL .. because when I solved this problem I reduced the above sum into a function of the the prime factorization and hence I could evaluate it in O(log x) for any x

»
3 years ago, # |
Rev. 2   Vote: I like it +10 Vote: I do not like it

The main claim is that the sum is .

This can be proved easily since there are exactly numbers with and i ≤ n.

Now, since dφ (d) is a multiplicative function, so is f(n).

Therefore, we can calculate f for prime powers and multiply the results to get f(n).

It turns out — that .

Now, preprocessing the Eratosthenes's Sieve in , we can now perform prime factorization in . It is easy to calculate f once we have the prime factorization.

Therefore, the time complexity is which is good enough to pass.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I solved it using Pillai's Arithmetic Formula.

Since gcd(i, N)1 <  = i <  = N is one of the divisors of N hence in order to compute the summation we need to find the sum . Now we need to find freq(d) .We need to find the number of i's such that gcd(i, N) = d hence i = d * j when you substitute this in the previous equation you'll get this gcd(j, N / d) = 1 . This equation means that we need to find the number of numbers less than N / d that are coprime with N / d . This is called Euler's totient function.That is how you get this equation

Now coming to the codechef problem , the only change that you need to make is to substitute d with N / d . Hence the sum now becomes which same as writing

Try solving now.