コンテスト中には解けなかったけど，おもしろかったので記事に残しておきます
オーバーフロー指摘して，助けてくれた某さん本当にありがとうございました．
問題のリンク
codeforces.com
問題概要
n，k(1<=k<=n<=1018)が与えられる．1~nのすべての数(xとする)に関して，偶数なら割る2，奇数なら引く1を1になるまで繰り返す．すべて操作し，登場回数がk回以上になる数のうち最大の数を出力する．
例えば(n=7，k=3)なら操作は以下のようになる
7 | 1 <- 2 <- 3 <- 6 <- 7
6 | 1 <- 2 <- 3 <- 6
5 | 1 <- 2 <- 4 <- 5
4 | 1 <- 2 <- 4
3 | 1 <- 2 <- 3
2 | 1 <- 2
1 | 1
よって3回以上登場する数の中で最大なのは3なので答えは3．
コンテスト中
とりあえずnとkが1018までってデカすぎるだろ正気か？となる->
まぁでもデータ構造は何も使えないだろうからどこかで単調性を見つけて二分法をするんだろうと思う->
とりあえず実験をいろいろやってみると，偶数と奇数で動きがちょっと違うけど↓こんな感じに式で表せそうと気付く
iの登場回数をg(i)とすると
g(i) = 0 (i>n)
g(i) = 1 + g(2i) (i:odd)
g(i) = 1 + g(2i) + g(i+1) (i:even)
1というのはi自体が登場することを言っており，iが奇数であれば2iからiになることを考えれば2iの数はすべてiに遷移するので2*iの登場回数を加えればいいです．偶数も同様に遷移を考えると上のようになります．1つ目の式を考えると上の式を愚直に再起で回せば各数の登場回数が求まりそう！
->証明は後述しますが，偶奇でそれぞれiが大きくなればg(i)は小さくなるという単調性があることに気づきます．
これを使ってg(i)がkを超えるかの境目を二分法を偶奇それぞれで探して，いいほうを出力するコードを提出します！
Submission #66962483 - Codeforces
-> TLE...（´・ω...:.;::..ｻﾗｻﾗ...
まぁそれはそうなんですよね，これめちゃくちゃ大量に再起するし，詳しい計算量解析はちょっと難しくてわからないけど，実験してみたらすげぇことになった(語彙)
コンテスト後にわかったこと
奇数の方は再起関数を使わなくても登場回数がわかるんですね．
まず，割る2するという操作はビットを1右シフトするという操作であることを考えると，一連の操作はビットで考えるとわかりやすいです．
操作は，11101->11100->1110->111->110->11->10->1 のように行われます．
最右桁を1から0にしてその0を消す．を繰り返すんですね．
このことを考えると，例えば3 (11)の登場回数は1~nの中の上位ビットが11となっている数の個数になります．
11XXXXXという数なら先ほどの操作を繰り返せばいずれ11になります．逆にそうじゃない数からは11に遷移することはありません．
よって奇数の方のg(i)はビットを考えてあげるとlog(i)で求まります．
よって奇数の方は先ほど言った単調性も成り立ちます．
偶数のほう，例えば110の登場回数は上位ビットが110もしくは111になるような数の個数になります．
これを考えると偶数のほうも単調性が成り立ち，二分法が可能そうです．
偶数のほうもいい感じに改良できるのかな？と思いましたが，偶数のほうはそのまま再起のままでとりあえず出してみたら通りました．(おい）
↓がその提出です．
まとめ
コドフォ最高！
