質問: int(input()) print((k // 2) * ((k + 1) // 2)) ``` ``` print(int(input()) ** 2 >> 2) ```
回答: kが奇数なら ・`k // 2 == (k - 1) / 2` ・`((k + 1) // 2) == (k + 1) / 2` 問題の答えは`((k - 1) * (k + 1)) / 4 == (k ** 2 - 1) / 4 == k ** 2 // 2 / 2`(※) ※: kが奇数なので`k ** 2`も奇数だから `(k ** 2 - 1) / 4` は`k ** 2`の下位1ビットを無視して4で除算することと同じと考えることができる kが偶数なら ・`k // 2 == k / 2` ・`((k + 1) // 2) == k / 2` ・問題の答えは`(k / 2) * (k / 2) == k ** 2 / 4` つまりkの偶奇によらず問題の答えは`k ** 2`をあまりを無視して4で割ることと同じ...つまり `k ** 2 >> 2` ということになるわけです。 上記の奇数のときの論理が不十分だったので訂正します: k(奇数)より1小さい偶数をeとすると `k ** 2 == (e + 1) ** 2 == e ** 2 + 2 * e + 1` eは偶数なので`e ** 2`は偶数、`2 * e`も偶数。よって`e ** 2 + e * 2`は必ず4の倍数になる。 つまりkが奇数の時、`k ** 2`のLSB(下位1ビット)は必ず1で、LSBの一つ上の桁のビットは必ず0になる。 故に`(k ** 2 - 1) / 4 == k ** 2 >> 2`と同じとなる