次元LAB

题干

次元LAB来啦！

马上就要召开音乐节，主办方邀请了 $n$ 位嘉宾，为了确定演出顺序，$n$ 位嘉宾围成一圈，嘉宾间进行投票， $nakotanmaru$ （简称 $nako$ ）作为嘉宾之一，嘉良想要将她安排在最后一个节目作为压台节目！因此设置了特定的投票规则。

假设每个嘉宾之表演一个节目，每个节目只需要一个嘉宾来表演，投票规则如下：

将 $n$ 位嘉宾进行编号为 $1,2,3\cdots,n$ ，初始大家都在投票区。
投票从 $1$ 开始，按标号顺序投票，每个嘉宾投票完立刻公布自己投票内容，因此每个嘉宾一定会投票。
在任何时候，嘉宾有了 $k$ 票，那么嘉宾将会走到确定区，并且不参与剩下的投票环节。
嘉宾只能投向当前情况下自己右手边的嘉宾（假设主办方邀请了 $5$ 个嘉宾，当前剩余嘉宾为 $1,3,5$ ，如果现在轮到 $1$ 投票，$1$ 只能投给 $3$ ；如果现在轮到 $3$ 投票，$3$ 只能投票给 $5$ ；如果现在轮到 $5$ 投票，$5$ 只能投票给 $1$ 。
演出顺序根据走到确定区的顺序确定，最先到确定区的嘉宾第一个表演，最后到确定区的嘉宾倒数第二个表演。
投票一直进行，直到当投票区只有 $1$ 名嘉宾时，此时，投票结束，投票区的最后 $1$ 名嘉宾将会作为压台节目的表演者！

为了满足嘉良的愿望——让 $nako$ 表演压台节目，他想知道，排座位时需要将 $nako $ 座位设置为多少号可以满足自己的愿望。

换种说法，当 $nako$ 座位号为多少时，她会表演压台节目？

eba16ce8c4fdd0e55b8743ed6e5e7005262995951

输入格式

输入两个整数 $n$ 和 $k$

其中 $1\le n,k\le 10^{18}$ 。

输出格式

输出一个整数，代表当 $nako$ 的座位号为这个数字时，会表演压台节目。

样例输入

10 1

样例输出

样例解释

样例中，嘉宾为 $10$ 人，$k=1$ 。

第 $1$ 次投票： $1$ -> $2$。

第 $2$ 次投票： $3$ -> $4$。

第 $3$ 次投票： $5$ -> $6$。

第 $4$ 次投票： $7$ -> $8$。

第 $5$ 次投票： $9$ -> $10$。

第 $6$ 次投票： $1$ -> $3$。

第 $7$ 次投票： $5$ -> $7$。

第 $8$ 次投票： $9$ -> $1$。

第 $9$ 次投票： $5$ -> $9$。

最终，投票区只剩下 $5$ ，因此答案为 $5$ 。

题解

在本题中，每个人必须投票，则在第一个人到达 $k$ 票之前的瞬间时，所有人的票数一定是相等的，因此， $k$ 值对于结果没有任何影响，不论 $k$ 值为多少，我们可以直接看作为 $1$ 。

于是现在问题转化为：

$N$ 个人坐成一个圆环（编号为 $1-N$ ），从第 $1$ 个人开始报数，数到 $2$ 的人出列，后面的人重新从 $1$ 开始报数。问最后剩下的人的编号。

直接模拟

如果不消除 $k$ 的影响，一定会导致 $TLE$

但是即使消除了 $k$ 值的影响，因为 $1\le N\le10^{18}$ 也会因为 $N$ 值的扩大而 $TLE$ 。所以对于 $N$ 值不大的数据可以混分，对于 $N$ 值过大的数据需要思考其原理，我们分为 $N=2^i$ 和 $N=2^i+M(1<M<2^i)$ 情况进行讨论。

$N$ = $2^i$ 的情况

最开始，从 $1$ 号开始，进行 $2^{i-1}$ 次操作后，场上将会剩下 $2^{i-1}$ 个嘉宾，并且下一次一定轮到 $1$ 号操作。

现在的情况为当 $N=2^{i-1}$ 时，并且从 $1$ 号开始操作，即为原题目 $N=2^{i-1}$ 的情况。

因此可以将 $N=2^i$ 转化为 $N=2^{i-1}$ 问题。

不断转化，直到 $N=2^0=1$ 时，场上只剩下 $1$ 号

因此当 $N=2^i$ 时， $1$ 号一定会留到最后。

$N=2^i+M(1<M<2^i)$ 的情况

在这种情况下，当进行 $M$ 次操作后，下一次操作的将会是 $2M+1$ 号，场上将会剩余 $2^i$ 个嘉宾。转化为 $N=2^i$ 情况，并且 $2M+1$ 号为新“ $1$ ”号。

因此当 $N=2^i+M(1<M<2^i)$ 时， $2M+1$ 号一定会留到最后。

结论

所以根据题目输入的 $n$ ，判断 $n$ 是否为 $2$ 的次方。

若是，直接输出 $1$ ；

若不是，则找到 $M$ ，输出 $2M+1$ ；（使用 $n-\lfloor\log_2n \rfloor$ 可以得到M）

约瑟夫环问题

本题其实是约瑟夫环问题的简化版本，可以思考一下：

$N$ 个人坐成一个圆环（编号为 $1-N$ ），从第 $1$ 个人开始报数，数到 $K$ 的人出列，后面的人重新从 $1$ 开始报数。问最后剩下的人的编号。

示例代码

#include <iostream>
#include <cmath>
#include <iomanip>
using namespace std;
#define int long long
double eps = 1e-9;
signed main()
{
    int n, k;
    cin >> n >> k;
    double log = log2(n);
    if (fabs(log - (int)log) < eps)
    {
        cout << 1 << endl;
    }
    else
    {
        cout << setprecision(18) << 2 * (n - powl(2, (int)log)) + 1 << endl;
    }
}