問題はこちら
No.638 Sum of "not power of 2" - yukicoder
考察により、答えは次のようになることがわかる
・Nが1,2,3,4,5,7のとき-1
・N-3が2ベキでないときa=3,b=N-3
・N-5が2ベキでないときa=5,b=N-5
正当性を示す。
2ベキでない最小の数は3、2番目に小さい数は5なので、1,2,3,4,5,7がダメなのは明らか。
よって「N≠1,2,3,4,5,7のとき、N-3とN-5がともに2ベキになることはない」を示せば良い。
差が2であるような2ベキの組は2,4しかなく、N≧8よりN-5>2、N-3>4であるから、これに該当することはない。
N-3が2ベキであるかどうかはpopcntが1であるかどうかを見れば良い
main(){ long n; scanf("%ld",&n); if(n<=5||n==7)puts("-1"); else if(__builtin_popcountl(n-3)!=1)printf("3 %ld",n-3); else printf("5 %ld",n-5); }
ところで、popcntを自前で実装するときの有名テクとして次のようなものがある
int popcnt(int n){ int count=0; while(n){ count++; n&=n–1; } return count; }
実はn&n-1により、nにおいて1になっている一番下のbitを消すことができる。
ということでpopcntを使わなくても、n-3&((n-3)-1)が0かどうかを見れば良いことが分かる。
long n; main(m){ scanf("%ld",&n); m=n-3&n-4?3:5; printf(n>5&&n-7?"%d %ld":"-1",m,n-m); }
83B