in this transition we r just doing this:
gcd(2i+1,4k+1+(2i+1)(2i-1))=gcd(2i+1,4k+1+(2i+1)(2i-1) - [(2i+1)(2i-1)])=gcd(2i+1,4k+1)
if we take it as gcd(a,b) we r basically doing this:
gcd(a,b)=gcd(a,b-(2i-1)a)
2 Likes
Got it. Thanks!
Mostly Cheat. Most Probably they saw the answer from youtube xD
I wasn’t able to get past TLE
But I made an observation and went all the way with it without thinking of a better approach.
For every prime number (n>2) the ans is n*6 .
Can someone elaborate how this is?
∑gcd(i,4∗K+1)=2∗E+4∗K+1
Tried to reduce ∑gcd(i,4∗K+1)
∑gcd(i, 4K+1){i=1..4K+1} = ∑gcd(i,4K+1){i=1..2K} + ∑gcd(i,4K+1){i=2K+1..4K} + 4K+1 = E + 4K+1 + ∑gcd(i,4K+1){i=2K+1..4K}
Not sure how ∑gcd(i, 4K+1){i=2K+1…4K} = E
I was able to make it to partially correct!..
https://www.codechef.com/viewsolution/46069076
this is the fasted I could go for with the solution of the first testcase in python. Can someone optimize this further? The finding of factors is itself so time consuming… idk if this even works in python.
Worst explanation ever.
Well, if you’re not ready to understand, no explanation will meet your requirements.
Why are you so prejudiced and toxic. First of all this is not 3d geometry or something complex to not understand. My point is when manipulating an equation you should write ‘since’ statements correctly. Secondly i actually understood the solution(where did i say i did not understand it). Next time don’t be toxic to people and don’t overestimate your skills. This is just number theory problems you are solving .
As one of the numbers is odd, the gcd will be odd no matter how much power of 2 is present as a factor of the other number as gcd is product of just the common factors.
because its answer got leaked on particular website:joy:
. More interestingly, participants who code in JAVA just submitted copied C++ code without even converting it.