Problem
My solution : solution
I was trying to solve this problem. It asks me to print phi(n) for n=a to b(inclusive). where,

0<a<b<10^14
and b-a<10^5
My solution is,
first do sieve and save all primes <= 10^7 in a vector prm. Then, run a segmented sieve to mark which ones are prime/composite in the range [a,b]. Then do another segmented sieve to calculate phi(n) in range [a,b].
I used long long(also tried unsigned long long) almost everywhere, but i'm getting WA. Can someone give me some corner cases/reason why I may be getting WA.
Thank you.

UVa 847 What's the idea behind solving this problem ? I can't solve it using dp as N could be very large . I was given hint : Choosing 9 is always optimal for Stan and Choosing 2 is always optimal for Ollie.But I can't prove it.

I have started to solve some Segment Tree problems recently and I had some queries about the Lazy Propagation Technique.

I understand the basic concept of Lazy Propagation and have solved some problems (all of them in the format : Add v to each element in the range [i,j] , Answer the sum , maximum/minimum element ,some info for elements in range [a,b]).

I got the concept for the adding element Lazy Propagation . But I have some confusion about changing the elements to v for all elements in the range [i,j] problem .

My question is , what is the general concept that I should have in mind while finding solution for these and more harder variations? I have seen lots of code online but they are mostly for the first version of the problem which I think I understand but I just don't know how to apply this concept to solve other variation of Lazy propagation problem.

And I also need some tips on debugging Segment tree problems.Thanks

Problem Type 1)

Lets say I have an array A[x1,x2,x3,...xN] of size N.

for N = 4 , A = {x1,x2,x3,x4}. [1 based index]

Now,I have to tell how many tuples (i,j) are there such that i<=j and cumulative sum(i,j) is divisible by K.

For example, N = 4

A = { 3,2,5,7} and K = 5.

Now , For this case the answer is 3. as, ( 1,2 ) [cum_sum = 5 ,divisible by K(5)], (3,3) [cum_sum = 5 ,divisible by K(5)] , (1,3) [ cum_sum = 10 ,divisible by K(5)] are such tuples.

I can do this in O(N^2) easily.But how to do this in O(N) or O(N*log(N)) ?

Please give me some problem links based on this (or similar) idea/trick from CodeForces.