Hello! Thank you for showing us this editorial! It's really crazy how we can simply reform this problem into a sieve problem. I thought of some principle of inclusion-exclusion magic aswell, but deemed it as not feasible. Please, continue with these editorials, they are simply fabulous! I love especially how you thoroughly explain every step with proofs aswell - that's something others disregard. Take care!
I don't think so, but i m not sure there isnt a clever way to do it. Of course euler totient function will easily find all unordered coprims pairs but only over a range, but since we have discrete values here, i dont see how it can be done. Thank you for your comment, and please let me know if you find out how!
@@neatlystructured The answer to the problem is ∑ for k=1 to max(x[i]) of the function ( u(k) * C( d(k), 2 ) ) d(k) is the number of integers in given sequence that are divisible by k We see that this result comes from the Inclusion-Exclusion principle. The term in the summation corresponds to choosing two numbers which are multiples of k , and μ(k) decides whether we add it or not. Note that in inclusion-exclusion, we don’t consider k which aren’t square free, as it doesn’t add any effect to our answer. - I read it on cf edutorial, but I didn't understood much
![[CSES][Mathematics] Bracket Sequences I](http://i.ytimg.com/vi/oZHY0FeBFtw/mqdefault.jpg)
![[CSES][Mathematics] Bracket Sequences I](/img/tr.png)
![[CSES][Mathematics] Divisor Analysis](http://i.ytimg.com/vi/__21DNroCLo/mqdefault.jpg)
![[CSES][Mathematics] Prime Multiples](http://i.ytimg.com/vi/2UEYCzKXh1s/mqdefault.jpg)
Hello! Thank you for showing us this editorial! It's really crazy how we can simply reform this problem into a sieve problem. I thought of some principle of inclusion-exclusion magic aswell, but deemed it as not feasible. Please, continue with these editorials, they are simply fabulous! I love especially how you thoroughly explain every step with proofs aswell - that's something others disregard. Take care!
Very grateful for this mathematics playlist ! It's rare and precious
Thank you so much
How nicely u explained it, nothing could be better than this.Thanks a ton
Thank you so much
Very well presented my friend thank you. Had a lot of trouble understanding the solution of this problem until now.
Glad it helped!
Thnx for this wonderful lect
You are very welcome!
Can this also be solved using Mobius function or ETF? Is so, how?
I don't think so, but i m not sure there isnt a clever way to do it. Of course euler totient function will easily find all unordered coprims pairs but only over a range, but since we have discrete values here, i dont see how it can be done. Thank you for your comment, and please let me know if you find out how!
@@neatlystructured The answer to the problem is ∑ for k=1 to max(x[i]) of the function ( u(k) * C( d(k), 2 ) )
d(k) is the number of integers in given sequence that are divisible by k
We see that this result comes from the Inclusion-Exclusion principle. The term in the summation corresponds to choosing two numbers which are multiples of k
, and μ(k)
decides whether we add it or not. Note that in inclusion-exclusion, we don’t consider k
which aren’t square free, as it doesn’t add any effect to our answer.
- I read it on cf edutorial, but I didn't understood much
Can you provide lik to your submission?
sure here you go:
github.com/ars-longa-vita-brevis/CSES/blob/master/Mathematics/CountingCoprimePairs.cpp
sorry for late reply