We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
We have to compute Phi ( i ), if there is an integer j that j*(j+1)/2 = i .
We know that i <= 10^12 . Though, j can be up to 2*10^6 . For finding Phi ( i ), if i = a*b which gcd(a,b)=1 , we can see that phi ( i ) = phi(a)phi(b) . We can do that for j(j+1)/2 .
At last, we should make a prefix sum array with length of 2000000.
For answering to each query, we have to know the largest i that i*(i+1)/2 <= R and the smallest j that j*(j+1)/2 >= L . The answer will be prefix [ i ] - prefix [ j-1 ].
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
A Weird Function
You are viewing a single comment's thread. Return to all comments →
At first, find primes up to 2000000 with [linear seive of eratosten] .(https://cp-algorithms.com/algebra/prime-sieve-linear.html)
We have to compute Phi ( i ), if there is an integer j that j*(j+1)/2 = i . We know that i <= 10^12 . Though, j can be up to 2*10^6 . For finding Phi ( i ), if i = a*b which gcd(a,b)=1 , we can see that phi ( i ) = phi(a)phi(b) . We can do that for j(j+1)/2 . At last, we should make a prefix sum array with length of 2000000. For answering to each query, we have to know the largest i that i*(i+1)/2 <= R and the smallest j that j*(j+1)/2 >= L . The answer will be prefix [ i ] - prefix [ j-1 ].