yukicoder : No.589 Counting Even

証明なしで実験で回答するの、人によって好き嫌いありそう。
https://yukicoder.me/problems/no/589

問題

整数Nが与えられる。となるiのうちが偶数となるのはいくつか。

解法

実験してみると、が奇数となるのは2のpopcount(N)乗であることがわかる。
よって(N+1)からそれを引けばよい。

この特徴については、いくつかのサイトで言及があるね。

A048967 - OEIS
https://www.math.hmc.edu/funfacts/ffiles/30001.4-5.shtml
Art of Problem Solving

ll N;


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	
	x=__builtin_popcountll(N);
	cout<<(N+1)-(1LL<<x)<<endl;
}

まとめ

最初は頑張って求めようかと思ってたよ。