ABC356D

問題

ABC356D

解法

ビット毎に独立して計算できることと，和の順序を入れ替えられる事に気を付ける．

まず，簡単のために $N$ が 2冪のときを考える．
$N = 2^{i+1}$ とすると，$2^{i}$ の桁が 1になるのは $2^{i}$ 個．
なぜなら，2進数で表記すると，$2^{i}$個の 0と $2^{i}$個の 1が交互に並ぶから．

次に，$N$ が 2冪の倍数とする．
$N = 2^{i+1} * q$ とすると，$2^{i}$ の桁が 1 になるのが $2^{i} \cdot q$ 個．
また，同じ数だけ 0 も出てくる．

最後に，$N$が自然数とする．$2^{i+1}$ でサイクルになっていることに注意すればよい．

$$0\cdots01\cdots10\cdots01\cdots1\cdots$$

のサイクルになっている．
よって，$cyc := 2^{i+1}$ で $N$ を割った商と余り $quo, rem$ を用いて求まる．

サイクルが割り切れる部分については，$2^{i}$の桁で 1になるものは $2^{i} \cdot quo$ 個．

余りの部分については，
$rem < 2^{i}$ のとき，$2^{i}$ の桁で 1になるものは 0個，
$rem \geq 2^{i}$ のとき，$rem - (2^{i} - 1)$ 個．

コード

main.cpp

ll f(ll i, ll n){
  ll cyc = 1LL << (i+1);
  ll rem = n % cyc;
  ll quo = n / cyc;

  ll ans = 0;
  ans += quo * (cyc / 2);
  ans += max(rem - ((cyc /2) -1), 0LL);
  return ans;
}

int main() {
  ll n,m;
  cin >> n >> m ;

  mint ans;
  rep(i,60){
    if(m >> i & 1)
      ans += f(i,n);
  }
  cout << ans.val() << endl;

  return 0;
}