ABC-105のC - Base -2 Number
前は解説を見ても解けなくて、久々に解説を見たら解けた。 公式以外の解説が検索でヒットしない?ように見える。
そもそも負数の余りって何？という話。
例えばだけど下のコードは何を表示するだろう。
私は-1だろうと思ったがそれは間違いらしい。
実際には2が表示される。まぁ0かどうか判定するなら困らないのかな・・・。
print( -10%3 )#=>?
pythonで負数%正の数をすると多分以下のコードと同じようなことなのだろう。 ちなみに下のコードだと-1が表示される。 C++だと負数であっても正の数と結果が変わらないようだ。 https://wandbox.org/permlink/cTNloRSLa3h8VdXGおまけ
def remain(n, base):
abs_n = abs(n)
return base - abs_n%base
ans = remain(-10,3)
print(ans)
print( -10%(-3) )#=>?
#include<iostream>
int main(){
std::cout << -10 % 3 <<"\n";//-1
std::cout << -10 % -3 <<"\n";//-1
return 0;
}
解説を読むと下から決められるらしい。
（問題文から下から決められそう！という感覚なり証明なり出来ないと難しい気がする）
上から決めていくのは難しそうな感覚はある。
(何か小さい数xを-2進数表現するときに、それが 2n - 2m (n != m; n%2==0; m%2==1 )のような表現で表すべき数であるなら何桁になるかすぐにはわからないように思う。
何桁になるかわからないということはそもそも最初、2nのnをどこから始めるのだろう。
適当に大きな数から開始して'0’は除く、とかでも良いのだろうけど。
)
下から決めるのは確かにうまくいくのだけどうまくいかないような気もする。
数nの余りを使ってnを調整?していく(nに足すか引く)ので、その後の処理で余りにはその値は含まれていない。
例えば、n%2の余りを使ってnを調整したら、n%4の値はn%2==0を満たす。
つまり n%pow(2,x) の余りrで調整したら、n%pow(2,x+1)の値はn%pow(2,x)==0を満たし、rを含まない。
これを繰り返すといずれはnは0になる。（そうなんだけどあまりしっくりしない）
調整の方向は、今bitのi桁目を決めているかで決められる。
- i % 2==0のとき
- nには正の数として加算されている
- したがって調整時には減算
- i % 2 == 1
- nには負の数として加算されている
- したがって調整時には加算
