problem-solved's blog

By problem-solved, 12 years ago, In English

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 )
  • Vote: I like it
  • +5
  • Vote: I do not like it

»
12 years ago, # |
  Vote: I like it -15 Vote: I do not like it

最后一种情况感觉你只证明了大于的情况不行,但是并没有证明小于的情况为什么正确的把?

  • »
    »
    12 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    Could you speak English please?

    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      "Last case i feel it only proved that greater is not, but it did not prove why less than correct?"

    • »
      »
      »
      12 years ago, # ^ |
      Rev. 2   Vote: I like it -10 Vote: I do not like it

      China Qingdao。。。英文不好伤不起啊。。。额额额额。。。

      • »
        »
        »
        »
        12 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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

        • »
          »
          »
          »
          »
          12 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          没有。。我意思是前面的都给出了证明,对于最后一种情况没有证明为什么是对的啊。。只是给出这个例子说明,但是不能保证通项把?

          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

          • »
            »
            »
            »
            »
            »
            12 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            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

        • »
          »
          »
          »
          »
          12 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          额。。。望大神指教啊。。。

»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

"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.