yukicoder No.638 Sum of "not power of 2"

この記事は yukicoder No.638 Sum of "not power of 2" の解説です。

a をなるべく小さくしたいので、可能なら a=3 にしたい。
b のとりうる最小値も a と同じく 3 なので、6=3+3 よりも小さい N は N=a+b で表せない。

以下、N≧6 について考える。

a=3 としたときに b=N-3 が 2 の整数乗でないという条件を満たしていれば、求める (a, b) の組は (3, N-3) である。
そうでないとき、a=5 とすると b=N-5 が条件を満たさないことはほとんどない。
なぜならば、N-3 と N-5（という、差が 2 であるような 2 数の組）がともに 2 の整数乗であるので、これを満たすような 2 数の組は (N-3, N-5) = (4, 2) 以外に存在しないからである。
つまり、N=7 のときは a=3 も a=5 もダメで、N≠7 のとき、求める (a, b) の組は (5, N-5) である。

まとめると、

• N<6 または N=7 のとき -1
• そうでないとき a=3 が OK なら (a, b) = (3, N-3)
• そうでないとき (a, b) = (5, N-5)

となる。

「正の整数 x が 2 の整数乗である」は (x & x-1) == 0 で判定できる。

#232871

ll N;
{
	rd(N);
	if(N<6||N==7)
		wt(-1);
	else if(N-3&N-4)
		wt(3,N-3);
	else
		wt(5,N-5);
}