Cows and Cool Sequences maybe this proof is easy for you ,but for me .... hehe....so I wrote this ... my english is so poor,so i can't understand the Tutorial I think most of you can come up with the idea of DP,but be confused with the proof of how to judge whether a cool sequence can begin with a[i] and ends with a[j] . Proof: first : a conclusion

if(x,y) is cool 
      if(y is odd) then x%y=0
      else (2*x%y==0 && x%y!=0)

proof : provided that the first number of the sequence is t ,so

x = y*(y-1)/2 + y * t

if y is odd, ( y — 1) is even ,so x = y*((y-1)/2+t),so if (x,y) is cool x must be divided by y if y is even, y-1 is odd so

 2*x = y*(y-1) + 2*y*t  ;
2*x = y*( (y-1)+2*y*t ); 

so 2*x must be divided by y ,but another x can't be divided by y(because 2*y*t is odd)

and there is also another important conclusion when y is even ,that is m[y] = m[x] + 1; (m[n] denote the exponent of the largest power of 2 that divides n.) this is also easy to prove :

a[i] = 2^a * p  
2*a[i] = 2^(a+1)*p
a[j] = 2^b*q
(p,q are the biggest odd factor ) 
since a[j] can divided 2*a[i] and a[j] can't divided a[i],we can conclude b = a + 1;

we can solve the problem , no matter what's the parity of a[j] , there's a big condition must be fullfilled:

the max odd factor of a[i] must be divided by the max odd factoe of a[j]

if a[j] is odd ,and a[i]%a[j]==0,we can always construct the sequence

,for example a[i]=12  a[j] = 3,we can construct the sequence like 
12 3 ...3 3 3 3  3 3 3 3.

if a[j] is even , given that m[u] = m[u-1] + 1. so m[j] = m[i] + j — i; it's the situation that all of the numbers in the cool sequence(except a[i]) are even

for example :a[i] = 3,a[j] = 36  ,the sequence is : 3 6 12 24 36

the last situation is there are some odd numbers in the left part of the sequence ,and then even numbers ..

what's the condition of this situation that ensures there's a cool sequence ? it's easy now :

m[j] <= j -i - 1;

for example : a[i] = 6,a[j] = 24; cool sequence :  6 3 3 3  3 6 12 24

if m[j] > j — i — 1,there can't be any cool sequence begins with a[i],ends with a[j]. because m[i+1] = m[j] — (j — i -1) > 0 since a[i],a[i+1] must be cool and a[i+1] is even ,so

m[i+1] = m[j] - j - i - 1 
m[i] < m[i+1] , m[i]+1 >= m[j]-(j-i-1)
so m[i] == m[j] - (j-i) -> m[i] + j - i = m[j]
(so here coms a contradiction ，it's already judged in the case up ）