Can anyone provide an explanation for this problem!! I am not able to understand the basic idea.
Can anyone provide an explanation for this problem!! I am not able to understand the basic idea.
№ | Пользователь | Рейтинг |
---|---|---|
1 | tourist | 3843 |
2 | jiangly | 3705 |
3 | Benq | 3628 |
4 | orzdevinwang | 3571 |
5 | Geothermal | 3569 |
5 | cnnfls_csy | 3569 |
7 | jqdai0815 | 3530 |
8 | ecnerwala | 3499 |
9 | gyh20 | 3447 |
10 | Rebelz | 3409 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | maomao90 | 171 |
2 | awoo | 163 |
3 | adamant | 162 |
4 | TheScrasse | 157 |
5 | nor | 153 |
6 | maroonrk | 152 |
6 | -is-this-fft- | 152 |
8 | Petr | 146 |
9 | orz | 145 |
10 | pajenegod | 144 |
Название |
---|
the sum =![](https://espresso.codeforces.com/3559c5fb284430e5fa4ae28a421b59d4b53e5ca3.png)
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
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.
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 ![](https://espresso.codeforces.com/4ecbe48d4b5bf2b23542b83c337759c27c367265.png)
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 ![](https://espresso.codeforces.com/21ed0bbe4ccdd50b6bd0c3f8af45d74703eeff63.png)
Try solving now.
i implemented what Noureldin and bhishma are talking about but i am getting TLE. here is my code what i did found totient[i] — n loglogn compute ans[i] — that too is n loglogn