問題一覧 > 通常問題

No.3554 Rurumaru Function Problem 2

レベル : / AI推定難易度 : 2600 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 1024 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 16
作問者 : ルク / テスター : 👑 loop0919 ぽえ lif4635
お気に入りにしたユーザー ProblemId : 13321 / 自分の提出
問題文最終更新日: 2026-04-23 21:48:05
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 500 (順位表) の他の問題:

Problem Statement

For non-negative integers $x,y$, let $f(x,y)$ be the non-negative integer defined as follows.
  • The value of the $2^i(i \ge 0)$'s place of $f(x,y)$ in binary is:
    • if $i$ is even, the logical AND of the value of the $2^i$'s place of $x$ and the value of the $2^i$'s place of $y$.
    • if $i$ is odd, the logical OR of the value of the $2^i$'s place of $x$ and the value of the $2^i$'s place of $y$.
For example, $f(2,14)=10$. (In binary, $f(0010_{(2)},1110_{(2)})=1010_{(2)}$.)
Also, for a positive integer $n$, define $g(n)$ as follows.
  • Consider the values of $f(x,y)$ for all pairs of integers $(x,y)$ satisfying $0\le{x,y}\lt{n}$. Let $g(n)$ be the smallest among the modes of these $n^2$ values.
You are given a positive integer $N$. Find $\displaystyle\sum_{n=1}^N {g(n)}$.

Constraints

  • $1 \le N \le 10^9$
  • All inputs are integers.

Input

The input is given from standard input in the following format.

$N$

Output

Output the answer.

Sample

Sample 1
Input
4
Output
4
The following are the values of $f(x,y)$ for all pairs of integers $(x,y)$ satisfying $0\le{x,y}\le{N-1}$.
$f(0, 0) = 0$, $f(0, 1) = 0$, $f(0, 2) = 2$, $f(0, 3) = 2$
$f(1, 0) = 0$, $f(1, 1) = 1$, $f(1, 2) = 2$, $f(1, 3) = 3$
$f(2, 0) = 2$, $f(2, 1) = 2$, $f(2, 2) = 2$, $f(2, 3) = 2$
$f(3, 0) = 2$, $f(3, 1) = 3$, $f(3, 2) = 2$, $f(3, 3) = 3$
  • For $g(1)$, the mode of $[f(0,0)]=[0]$ is $0$, so $g(1)=0$.
  • For $g(2)$, the mode of $[f(0,0),f(0,1),f(1,0),f(1,1)]=[0,0,0,1]$ is $0$, so $g(2)=0$.
  • For $g(3)$, the mode of $[0,0,2,0,1,2,2,2,2]$ is $2$, so $g(3)=2$.
  • For $g(4)$, the mode of $[0,0,2,2,0,1,2,3,2,2,2,2,2,3,2,3]$ is $2$, so $g(4)=2$.
Therefore, the value to find is $g(1)+g(2)+g(3)+g(4)=4$.
Sample 2
Input
1
Output
0

Sample 3
Input
1000000000
Output
303611125277312236

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。