Gettting TLE =, cant come with solution
my solution
GEtting TLE, for ETF QuERY problem from dynamic programming course
@sohampatil_sp
hello soham
phi(n)=n * (1-1/p1) * (1-1/p2) * (1-1/p3)… where p1,p2,…pi are prime factors of n right?
so what we will do is . we will maintain an array of maximize size possible say dp .
and initially fill ith position with value i. ie dp[i]=i;
now we will use same sieve logic . if dp[i]=i it mean i is a prime number so we will update its answer with i-1 and will go to all its multiple (say j) and will do dp[j]=dp[j]*(1-1/i)
once sieve logic is done .
we will compute prefix sum.
and for each query i.e l ,r
we will print dp[r]-dp[l-1]