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 )
最后一种情况感觉你只证明了大于的情况不行,但是并没有证明小于的情况为什么正确的把?
Could you speak English please?
"Last case i feel it only proved that greater is not, but it did not prove why less than correct?"
China Qingdao。。。英文不好伤不起啊。。。额额额额。。。
it's obvious,we can construct the sequence like this a[i] odd odd odd odd even even even even a[j] like the example : 6 3 3 3 3 6 12 24
没有。。我意思是前面的都给出了证明,对于最后一种情况没有证明为什么是对的啊。。只是给出这个例子说明,但是不能保证通项把?
i mean it did not proved to be true.because it just a sample test,it can not approve it to the all the conditions
m[j] <= j -i — 1; means that you can continue to divided a[j] by 2 until is becomes an odd number in the middle of the sequence,and a[i] can be divided by this odd number
thanks very much!!!!!
额。。。望大神指教啊。。。
"Last case feel you onlyproved greater than not, but does not prove why less than correct?" This is the translation of luyuncheng's comment in english.
thanks for translate