n = int(raw_input())
print int(bin(n).replace('1','0',1), 2)<<1|1

基本思路：
1、减治法，找到递推公式
2、字符串模拟
设m为总人数，J(m)为最后存活编号，存在递推关系：
J(m) = 2J(m/2)+-1，其中当m为偶数时-1，当m为奇数时+1。边界条件：J(1)=1.
然后定义字符串的乘法、除法和+1、-1算法，利用递归函数即可求解。
具体算法参照Levitin《算法设计与分析基础》

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
//int Joseph(int x)
//{
//    if (x == 1) return 1;
//    else{
//        if(x % 2) return 2 * Joseph(x/2) + 1;
//        else return 2 * Joseph(x/2) - 1;
//    }
//}用整数来解释算法：基于递推的约瑟夫算法
char* Div2(char x[], int n);//÷2算法
char* Mult2(char x[], int n);//×2算法
int ModEven(char c);   //判断是否为奇数
char* Joseph(char x[], char cmp[], int n);//核心算法
char* Min1(char x[], int n);//-1算法
char* Plus1(char x[], int);//+1算法

int main()
{
    int n, p;
    char x[101] = {0};
    char *target;
    x[100] = '\0';
    gets(x);
    for(n = 0; x[n] != '\0'; n++); //n为位数
    char cmp[101] = {0};
    int i;
    for(i = 0; i < 100; i++){
        cmp[i] = '0';
    }
    cmp[n] = '\0'; cmp[n - 1] = '1';    //初始化比较字符串cmp
    target = Joseph(x, cmp, n);
    for(i = 0; i < n; i++){
        if(target[i] != '0') break;
    }
    for(p = i; p < n; p++){             //删除前面不需要的占位0
        printf("%c", target[p]);
    }
    printf("\n");
    return 0;
}

int ModEven(char c)
{                                   // 判断该数是否为奇数
    int d = (c - '0') % 2;
    if (d) return 1;
    else return 0;
}

char* Mult2(char x[], int n)        //定义字符串乘以2的算法
{
    int last, add = 0;   //最后一位的指标
    int unit;
    for(last = n - 1; last >= 0; last--){
        unit = 2 * (x[last] - '0');
        x[last] = unit % 10 + add + '0';
        if(unit > 9) add = 1;
        else add = 0;
    }
    return x;
}

char* Div2(char x[], int n)         //定义字符串除以2的算法
{
    int first, pre = 0;
    int tmp;
    for(first = 0; first < n; first++){
        tmp = x[first] - '0';
        x[first] = (pre * 10 + x[first] - '0') / 2 + '0';
        pre = (pre*10 + tmp) % 2;
    }
    return x;
}

char* Joseph(char x[], char cmp[], int n)       //核心函数
{
    char *tmp;
    char judgetmp;
    if(strcmp(cmp, x) == 0){
        return cmp;
        }//边界条件:J(1) = 1;
    else{
        judgetmp = x[n - 1];
        tmp = Mult2(Joseph(Div2(x, n), cmp, n), n);
        if(ModEven(judgetmp) == 0){
            return Min1(tmp, n);
        }
        if(ModEven(judgetmp) == 1){
            return Plus1(tmp, n);
        }
    }
    return x;
}

char* Min1(char x[], int n)                 //减一算法
{
    int last = n - 1;
    if(x[last] == '0'){
        for(x[last] = '9'; last > 0;){
            if(x[--last] == '0'){
                x[last] = '9';
            }
            else{
                x[last] -= 1;
                break;
            }
        }
    }else x[last] = x[last] - 1;
    return x;
}

char* Plus1(char x[], int n)            //加一算法
{
    int last = n - 1;
    if(x[last] == '9'){
        for(x[last] = '0'; last >= 0;){
            if(x[--last] == '9'){
                x[last] = '0';
            }
            else{
                x[last] += 1;
            }
        }
    }
    else{
        x[last] += 1;
    }
    return x;
}

公式为：ans=2*(n-2^k)+1(k为使2^k小于n的最大整数）
使用高精度加减乘运算以上公式即可。
公式由来：当n为2的整数倍时，最后留下的人一定是1；
当n不为2的整数倍时，设n=2^k+t(任何一个正整数都可以用2^k+t(t为任意正整数)来表示），
即去掉t个人后为n=2的整数倍情况，而每一次去掉第m(m<=t)的人的编号为2*m(报到2的出列），
所以方程移项再加1即为所求ans。
整个公式就推出来了。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
const int maxn=101;

int l=1,len;
int a[maxn],t[maxn];
string s;

bool cmp()
{
int f=1;
if(l<len)
return true;
if(l>len)
return false;
for(int i=len;i>=1;i--)
{
if(t[i]<a[i])
return true;
if(t[i]>a[i])
return false;
if((t[i]==a[i])&&(i==1))
return true;
}
}

void cf()
{
for(int i=1;i<=l;i++)
t[i]=2*t[i];
for(int i=1;i<=l;i++)
{
if(t[i]>=10)
{
t[i+1]+=t[i]/10;
t[i]%=10;
}
}
if(t[l+1]>0)
l++;
}

void add()
{
a[1]+=1;
for(int i=1;i<=len;i++)
if(a[i]>=10)
{
a[i+1]+=a[i]/10;
a[i]%=10;
}
if(a[len+1]>0)
len++;
}

void jf()
{
for(int i=1;i<=len;i++)
{
if(a[i]<t[i])
{
a[i+1]--;
a[i]+=10;
}
a[i]=a[i]-t[i];
}
if(a[len]==0)
len--;
}

main()
{
memset(a,0,sizeof(a));
memset(t,0,sizeof(t));
cin>>s;
len=s.size() ;
for(int i=0;i<len;i++)
a[len-i]=s[i]-'0';
if((len==1)&&(a[1]<=2))
cout<<'1'<<endl;
else if((len==1)&&(a[1]==3))
cout<<'3'<<endl;
else
{
t[1]=2;
while(1)
{
cf();
if(!cmp())
break;
}
for(int i=1;i<=len;i++)
a[i]=a[i]*2;
for(int i=1;i<=len;i++)
if(a[i]>=10)
{
a[i+1]+=a[i]/10;
a[i]%=10;
}
if(a[len+1]>0)
len++;
jf();
add();
while(a[len]==0)
len--;
for(int i=len;i>=1;i--)
cout<<a[i];
cout<<endl;
}
return 0;
}

高精度+递推

#include <bits/stdc++.h>
using namespace std;
#define FOR(i,n) for (int i=1;i<=n;i++)
#define REP(i,a,b) for (int i=a;i<=b;i++)
#define pb push_back
#define mp make_pair
#define ll long long
const int N=100000+10;
const int inf=0x3f3f3f3f;
const ll mod=7654321;
const double PI=3.1415926;
const double eps=1e-8;

string s;
struct bignum {
    int len;
    int a[201];
    bignum() {
        len=0;
        memset(a,0,sizeof a);
    }
    void operator=(bignum x) {
        len=x.len;
        FOR(i,len) a[i]=x.a[i];
    }
    bool operator==(bignum x) {
        if (len!=x.len) return 0;
        FOR(i,len) if (a[i]!=x.a[i]) return 0;
        return 1;
    }
    bool operator<(bignum x) {
        if (len<x.len) return 1;
        else if (len>x.len) return 0;
        for (int i=len;i>=1;i--) {
            if (a[i]<x.a[i]) return 1;
            else if (a[i]>x.a[i]) return 0;
        }
        return 0;
    }
    bool operator<=(bignum x) {
        return (*this)<x||(*this)==x;
    }
    bignum operator+(bignum x) {
        bignum res;
        res.len=max(x.len,len);
        FOR(i,res.len) {
            res.a[i]+=a[i]+x.a[i];
            if (res.a[i]>9) {
                res.a[i+1]+=res.a[i]/10;
                res.a[i]%=10;
            }
        }
        if (res.a[res.len+1]) res.len++;
        return res;
    }
    bignum operator-(bignum x) {
        bignum res;
        res.len=max(x.len,len);
        FOR(i,res.len) res.a[i]=a[i]-x.a[i];
        FOR(i,res.len) {
            if (res.a[i]<0) {
                res.a[i+1]--;
                res.a[i]+=10;
            }
        }
        while (res.len>1&&!res.a[res.len]) res.len--;
        return res;
    }
    bignum operator*(bignum x) {
        bignum res;
        res.len=len+x.len-1;
        FOR(i,len) FOR(j,x.len) {
            res.a[i+j-1]+=a[i]*x.a[j];
        }
        FOR(i,res.len) {
            if (res.a[i]>9) {
                res.a[i+1]+=res.a[i]/10;
                res.a[i]%=10;
            }
        }
        if (res.a[res.len+1]) res.len++;
        return res;
    }
    bignum operator/(bignum x);
    
} ten[101],num[10];
bignum bignum::operator/(bignum x) {
    // 要保证能整除 
    bignum res,tmp;
    res.len=tmp.len=1;
    for (int i=100;i>=0;i--) {
        for (int j=9;j>=1;j--) {
            if (x*(tmp+ten[i]*num[j])<=(*this)) {
                tmp=tmp+ten[i]*num[j];
                res.a[i+1]=j;
                res.len=max(res.len,i+1);
                break;
            }
        }
    }
    return res;
}
void print(bignum x) {
    for (int i=x.len;i>=1;i--) cout<<x.a[i];
    cout<<endl;
}
bignum f(bignum x,int k) {
    if (x==num[1]) return num[1];
    if (k==0) {
        if (x.a[1]%2==0) {
            return num[2]*f(x/num[2],0)-num[1];
        } else {
            return num[2]*f((x+num[1])/num[2],1)-num[1];
        }
    } else {
        return f(x-num[1],0)+num[1];
    }
}
int main() {
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    REP(i,0,9) num[i].len=1,num[i].a[1]=i;
    ten[0].len=1,ten[0].a[1]=1;
    ten[1].len=2,ten[1].a[1]=0,ten[1].a[2]=1;
    REP(i,2,100) ten[i]=ten[i-1]*ten[1];

    string s2;
    cin>>s;
    //cin>>s2;
    bignum x,y;
    x.len=s.size();
    //y.len=s2.size();
    for (int i=0;i<s.size();i++) x.a[x.len-i]=s[i]-'0';
    //for (int i=0;i<s2.size();i++) y.a[y.len-i]=s2[i]-'0';
    print(f(x,0));
    return 0;
}

公式就不多说了,各位大佬已经说得很明白了
不过本题高精度实在是恶心，再加上我并不是特别熟练，代码写了170+行，有些地方有些冗杂
上代码：

#include <iostream>
#include <algorithm>
#include <stack>
#include <queue>
#include <memory.h>
using namespace std;

class BigInt{
public:
    int *a;
    int len;
public:
    BigInt(){}
    BigInt(string s){
        this->len = s.length();
        a = new int[len+1];
        for (int i = 1; i <= len; ++i)
            a[i] = s[len - i] - '0';
        a[0] = 0;
    }
    BigInt(int n){
        this->len = n;
        a = new int[n+1];
        memset(a,0, sizeof(a));
    }
    void show(){
        int k = len;
        while(a[k] == 0)
            k--;
        for (int i = k; i >= 1; --i) {
            cout << a[i];
        }
        cout << endl;
    }
    BigInt operator /(int b){
        BigInt r(len);
        for (int i = 1; i <= len; ++i) {
            r.a[i] = a[i];
        }
        int m;
        for (int i = r.len; i >= 1; --i) {
            m = r.a[i] % b;
            r.a[i] /= b;
            r.a[i-1] += m*10;
        }
        r.a[0] = m;
        int n = 0;
        for (int k = len; r.a[k] == 0 ; k--) {
            n++;
        }
        r.len -= n;
        return r;
    }
    int operator %(int b){
        BigInt r(len);
        for (int i = 1; i <= len; ++i) {
            r.a[i] = a[i];
        }
        r = r / b;
        return r.a[0];
    }
    BigInt operator +(BigInt b){
        int l = max(this->len , b.len);
        BigInt n1(l);
        BigInt n2;
        for (int i = 0; i <= l; ++i) {
            n1.a[i] = 0;
        }
        if(l == this->len)
        {
            for (int i = 1; i <= b.len; ++i) {
                n1.a[i] = b.a[i];
            }
            n2 = *this;
        }
        else{
            for (int i = 1; i <= this->len; ++i) {
                n1.a[i] = this->a[i];
            }
            n2 = b;
        }
        BigInt c(l+1);
        for (int i = 1; i <= l+1; ++i) {
            c.a[i] = 0;
        }
        for (int i = 1; i <= l; ++i) {
            c.a[i] += n1.a[i] + n2.a[i];
            c.a[i+1] += c.a[i] / 10;
            c.a[i] %= 10;
        }
        if(c.a[l+1] == 0)
            c.len --;
        return c;
    }
    BigInt operator *(int b){
        BigInt r(len+1);
        r.a[len+1] = 0;
        for (int i = 1; i <= len; ++i) {
            r.a[i] = a[i];
        }
        for (int i = 1; i <= len; ++i) {
            r.a[i] *= b;
        }
        for (int i = 1; i <= len; ++i) {
            r.a[i+1] += r.a[i] / 10;
            r.a[i] %= 10;
        }
        if(r.a[len+1] == 0)
            r.len --;
        return r;
    }
    bool operator >(BigInt n){
        if(this->len > n.len)
            return true;
        for (int i = len; i >= 1; --i) {
            if(this->a[i] == n.a[i])
                continue;
            return this->a[i] > n.a[i]?true:false;
        }
    }
};

BigInt pow(int a,int n){
    BigInt r("1");
    for (int i = 0; i < n; ++i) {
        r = r*a;
    }
    return r;
}

BigInt to_binary(BigInt n){
    queue<int> q;
    int m;
    while(n.len > 0) {
        m = n % 2;
        q.push(m);
        n = n / 2;
    }
    int len = q.size();
    BigInt r(len);
    for (int i = 1; i <= len; ++i) {
        r.a[i] = q.front();
        q.pop();
    }
    return r;
}

BigInt to_demcital(BigInt n){
    BigInt r("0");
    for (int i = 1; i <= n.len; ++i) {
        r = r + pow(2,i-1) * n.a[i];
    }
    return r;
}

int main()
{
    string s;
    cin >> s;
    BigInt a(s);
    BigInt b = to_binary(a);
    for (int i = b.len; i >= 1; --i) {
        if(b.a[i] == 1){
            b.a[i] = 0;
            break;
        }
    }
    BigInt ans = to_demcital(b);
    ans = ans * 2;
    ans.a[1]++;
    ans.show();

    return 0;
}

这个题实际上是有通项公式的,具体推导请看《具体数学》
J（2^m+K）=2*K+1
2^m+k是总人数，函数的结果是剩下的人的编号
设总人数为n
所以你只需要知道n展开成二进制之后的形式，并且把第一个“1”给置位成“0”
那么得到的结果就是k了
故:
结果=2*（~（1<<(位数-1)）&n）+1;

import java.math.BigInteger;
import java.util.Scanner;
public class Main {
    static Scanner in = new Scanner(System.in);
    public static void main(String[] args) {
        BigInteger n;
        n=in.nextBigInteger();
        BigInteger i=BigInteger.valueOf(1).shiftLeft(n.bitLength()-1);
        BigInteger answer=i.not().and(n).multiply(BigInteger.valueOf(2)).add(BigInteger.valueOf(1));
        System.out.println(answer);
    }
}

首先我写了一个程序，就想过3个点。
提交了后，我又想着打个表试试，说不定能得些分。
然后把程序挂起，打了个表，结果发现了规律。
部分表：
//--------------------------------------------------------------------
1,
1,3,
1,3,5,7,
1,3,5,7,9,11,13,15,
1,3,5,7,9,11,13,15,17,19,21,23,25,27,29,31,
1,3,5,7,9,11,13,15,17,19,21,23,25,27,29,31,33,35,37,39,41,43,45,47,49,51,53,55,57,59,61,63,
//---------------------------------------------------------------------
发现第一行1，第二行2个，第三行4个。第n行2^(n-1)个
第n行开头为第2^(n-1)个数
每行第k个数的值为2*k-1

思路：
高精度x低精度，每次乘完，比较一次n与上一行末尾的数、n与下一行开头的数的大小
得到n在不在该行中，不在就继续乘
如果在该行中，那么n就是该行第（n-上一行末尾的序号）个（高精度减法）
然后2k-1 得到结果 （高精度减法，乘法）
注：计算上一行末尾，即（2^n）-1时，直接在a[1] 减1即可。因为2的乘方末尾最小为2

代码
```c++
#include <cstdio>
#include <cstring>

int bigger(int a[],int b[]){
if(a[0]!=b[0])
return a[0]>b[0];
int flag=999;
for(int i=a[0];i>=1;i--)
if(a[i]!=b[i]){
flag=a[i]>b[i];
break;
}
if(flag==999)
return 0;
return flag;
}

int read(int a[]){
char c[1000];
scanf("%s",c);
int n=1,len=strlen(c),k=1;
for(int i=0;i<len;i++){
if(k==10000){
k=1;
n++;
}
a[n]+=k*(c[len-i-1]-'0');
k*=10;
}
a[0]=n;
}

int addx(int a[],int b[],int c[]){
int len=a[0]>b[0]?a[0]:b[0];
for(int i=1;i<=len;i++){
c[i]+=a[i]+b[i];
c[i+1]+=c[i]/10000;
c[i]%=10000;
}
len++;
while(c[len]==0&&len>1)
len--;
c[0]=len;
}

int minusx(int a[],int b[],int c[]){
int len=a[0];
for(int i=1;i<=len;i++){
c[i]+=a[i]-b[i];
if(c[i]<0){
c[i]+=10000;
c[i+1]-=1;
}
}
while(c[len]==0&&len>1)
len--;
c[0]=len;
}

void mult(int a[],int x){
int len,temp,k=0;
for(int i=1;i<=a[0]||k;i++){
temp=a[i]*x+k;
k=temp/10000;
a[i]=temp%10000;
len=i;
}
while(a[len]==0&&len>1)
len--;
a[0]=len;
}

void output(int a[]){
printf("%d",a[a[0]]);
for(int i=a[0]-1;i>=1;i--)
printf("%04d",a[i]);
}

int main(){
int n[100]={0};
read(n);
int flag;
int temp[100],base[100]={1,1};
while(1){
flag=1;
base[1]--;
flag*=bigger(n,base);
base[1]++;
memcpy(temp,base,sizeof(temp));//存放上一次

mult(base,2);
flag*=bigger(base,n);
if(flag)
break;
}
int c[100]={0};
temp[1]--;
minusx(n,temp,c);
mult(c,2);
int m[100]={1,1};
memset(temp,0,sizeof(temp));
minusx(c,m,temp);
output(temp);
return 0;
}

**附上打表代码**
c++
#include <cstdio>
#include <ctime>
#include <cstring>

int vis[10001]={0};

int main(){
freopen("output.txt","w",stdout);
for(int z=1;z<=10000;z++){
memset(vis,0,sizeof(vis));
int n,count=0;
n=z;
int now=1,next=1,kill=0;
while(count<n-1){
do
next=(next-1+1)%n+1;
while(vis[next]);
if(kill){
count++;
vis[now]=1;
kill=0;
}
else
kill=1;
now=next;
}
for(int i=1;i<=n;i++)
if(!vis[i])
printf("%d,",i);
}
return 0;
}
```

鄙人高精不好请见谅。。。
测试数据 #0: Accepted, time = 0 ms, mem = 808 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 804 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 808 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 804 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 808 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 804 KiB, score = 10
测试数据 #6: Accepted, time = 0 ms, mem = 804 KiB, score = 10
测试数据 #7: Accepted, time = 0 ms, mem = 808 KiB, score = 10
测试数据 #8: Accepted, time = 0 ms, mem = 804 KiB, score = 10
测试数据 #9: Accepted, time = 0 ms, mem = 804 KiB, score = 10
Accepted, time = 0 ms, mem = 808 KiB, score = 100
-------------------------------华丽的分割线-------------------------------
``` pascal
type int=longint;
var
s:string;
i,ls,t,f:int;
a,b,c:array[0..110]of int;
ff:boolean;
procedure double;
var
i:int;
begin
for i:=1 to ls+1 do
begin
a[i]:=b[i];
b[i]:=0;
end;
for i:=1 to ls+1 do
begin
b[i]:=b[i]+a[i]*2;
if b[i]>=10 then
begin
b[i+1]:=b[i+1]+(b[i] div 10);
b[i]:=b[i] mod 10;
end;
end;
end;

begin
readln(s); ls:=length(s);
for i:=1 to ls do val(s[ls+1-i],c[i]);
b[1]:=1; f:=0; ff:=true;
repeat
double;
until (b[ls]>=c[ls]) or (b[ls+1]>0);
if (b[ls]=c[ls]) and (b[ls+1]=0) then
for i:=ls-1 downto 1 do if b[i]>c[i] then
begin
f:=1;
break;
end else if b[i]<c[i] then
begin
f:=2;
break;
end;
for i:=1 to ls do if b[i]<>c[i] then ff:=false;
if ff then
begin
writeln(1);
halt;
end;
if f=2 then for i:=1 to ls+1 do a[i]:=b[i];
fillchar(b,sizeof(b),0);
for i:=1 to ls+1 do if c[i]<a[i] then
begin
b[i]:=c[i]+10-a[i];
dec(c[i+1]);
end else b[i]:=c[i]-a[i];
double;
inc(b[1]);
for i:=1 to ls+1 do if b[i]>=10 then
begin
b[i+1]:=b[i+1]+(b[i] div 10);
b[i]:=b[i] mod 10;
end;
t:=ls+2;
while b[t]<=0 do dec(t);
for i:=t downto 1 do write(b[i]);
writeln;
readln;
end.
```
健全的灵魂，寄宿生在健全的精神上，和健全的肉体上！！！

#include <cstdio>
#include <cstring>
using namespace std;
const int N=100+5;
int a[N],b[N]={0},c[N]={1,2},ans[N];
char ss[N];
bool pd(int h1[],int h2[]) //如果h1的数<=h2 则返回true

{
if(h1[0]<h2[0]) return true;
if(h1[0]>h2[0]) return false;
for(int i=h1[0];i>=1;i--)

if(h1[i]==h2[i]) continue;
else return h1[i]>h2[i]?false:true;
return true;
}
void turn_over()
{
int len=strlen(ss);
for(int i=0;i<len;i++)
a[i+1]=ss[len-i-1]-'0';
a[0]=len;
}
void mul(int s[])
{
for(int i=1;i<=b[0];i++) s[i]*=2;
for(int i=1;i<=s[0]+1;i++)
{s[i+1]+=s[i]/10;s[i]%=10;}
if(s[s[0]+1]) s[0]++;
}
void take()
{
for(int i=1;i<=a[0];i++)
{
if(a[i]<b[i]) {a[i]+=10;a[i+1]--; }
ans[i]=a[i]-b[i];
}
int i;
for(i=a[0]+1;ans[i]==0;i--); if(i<=0) i=1; ans[0]=i;
}
void add()
{
ans[1]++;
for(int i=1;i<=ans[0]+1;i++)
{ans[i+1]+=ans[i]/10;ans[i]%=10;}
if(ans[ans[0]+1]) ans[0]++;
}
int main()
{
scanf("%s",ss);
if(ss[0]=='1' && strlen(ss)==1) {printf("1");return 0; }
turn_over();
while(pd(b,a) && pd(c,a))
{
memcpy(b,c,sizeof(b));
mul(c);
}
take(); mul(ans);add();
for(int i=ans[0];i>=1;i--) printf("%d",ans[i]);
return 0;
}

通过一个模拟的程序找到了规律
设数列 an，a1=3，an=2*a（n-1）+1 .（递归定义，方便代码实现）
输入t
如果 t<=3 直接输出结果就好了
否则 找出这样的i，使得ai<n<=a(i+1)
ans = (n-ai)*2 - 1;

c++代码：
#include<bits/stdc++.h>
using namespace std;
struct BN{
int len,s[205];
BN(){
len = 0;
memset(s,0,sizeof(s));
}
BN operator -(const BN &x) const
{
BN y;
y.len = len;
for (int i = 1;i <= len;i++)
{
y.s[i] += s[i] - x.s[i];
if (y.s[i] < 0)
y.s[i] += 10,y.s[i+1] --;
}
while (y.s[y.len] == 0&&y.len > 1) y.len--;
return y;
}
bool operator >=(const BN &x) const
{
if (len != x.len) return len > x.len;
for (int i = len;i >= 1;i--)
if (s[i] != x.s[i]) return s[i] > x.s[i];
return true;
}
}a[400];
BN mul2(const BN &x)
{
BN y;
y.len = x.len;
for (int i = 1;i <= y.len; i++)
{
y.s[i] += x.s[i] * 2;
if (y.s[i] > 9) y.s[i] -= 10,y.s[i+1] ++;
}
if (y.s[y.len+1]) y.len++;
return y;
}
BN convert(string s)
{
BN y;
y.len = s.length();
for (int i = 0;i < y.len;i++)
y.s[y.len - i] = s[i] - '0';
return y;
}
void plus1(BN &y)
{
y.s[1] ++;
for (int i = 1;y.s[i] >= 10;i++)
y.s[i] -= 10,y.s[i+1] ++;
if (y.s[y.len+1] != 0) y.len++;
}
void minus1(BN &y)
{
y.s[1] --;
for (int i = 1;y.s[i] < 0;i++)
y.s[i] += 10, y.s[i+1] --;
if (y.s[y.len] == 0) y.len--;
}
void print(const BN &y)
{
for (int i = y.len;i >= 1;i--)
cout << y.s[i];
cout << endl;
}
int main()
{
int i;
string s;
BN n,ans;
cin >> s;
n = convert(s);

if (n.len == 1 && n.s[1] <= 3)
{
if (n.s[1] <= 2) cout << 1 << endl;
else cout << 3 << endl;
return 0;
}

a[0].len = 1,a[0].s[1] = 3;
for ( i = 1;;i++)
{
a[i] = mul2(a[i-1]);
plus1(a[i]);
if (a[i] >= n) break;
}
i--;
ans = mul2(n - a[i]) ;
minus1(ans);
print(ans);
return 0;
}
代码实现不难，主要是高精度
注意高精度声明时要初始化所有位上的数字为0，要不然进位会有问题(这点坑死我了！！)
还有 谁能严格证明或者不用归纳法直接推导出这个规律？有的回复一下谢谢

python万岁。参见楼下公式，不会证明，只能找规律...

n = int(raw_input())
left = 0
right = 1000
while left < right-1:
mid = (left+right)/2
if 2**mid > n:
right = mid-1
else:
left = mid
if 2**right <= n:
k = right
else:
k = left
print 2*(n-2**k)+1

当M=2时约瑟夫问题的解：
求出不大于N的最大的2的整数次幂，记为2^k，最后一个去死的人是2(N-2^k)+1

import java.math.BigInteger;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        BigInteger x = in.nextBigInteger();
        StringBuffer res = new StringBuffer(x.toString(2));
        res.deleteCharAt(0);
        res.append("0");
        x = new BigInteger(res.toString(),2);
        System.out.println(x.add(BigInteger.ONE));
        in.close();
    }
}

编译成功

foo.cpp: In function 'int main()':
foo.cpp:39:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<=strlen(s)-1;i++)
^
测试数据 #0: Accepted, time = 0 ms, mem = 388 KiB, score = 10
测试数据 #1: Accepted, time = 15 ms, mem = 384 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 388 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 384 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 384 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 384 KiB, score = 10
测试数据 #6: Accepted, time = 15 ms, mem = 384 KiB, score = 10
测试数据 #7: Accepted, time = 0 ms, mem = 388 KiB, score = 10
测试数据 #8: Accepted, time = 0 ms, mem = 384 KiB, score = 10
测试数据 #9: Accepted, time = 0 ms, mem = 384 KiB, score = 10
Accepted, time = 30 ms, mem = 388 KiB, score = 100

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string.h>
using namespace std;
char s[1100];
int num10[1100]; //存10十进制数
int num2[20100]; //存2进制数
int num_2[5010]; //存2的多次方
int max_2=1;
int ans[1100];
int maxans=1;
void aplus()
{
int in=0,i;
for(i=1;i<=max_2||in;i++)
{
ans[i]+=num_2[i]+in;
in=ans[i]/10;
ans[i]%=10;
}
maxans=max(maxans,i-1);
}
void multiply()
{
int in=0,i;
for(i=1;i<=max_2||in;i++)
{
num_2[i]*=2;
num_2[i]+=in;
in=num_2[i]/10;
num_2[i]%=10;
}
max_2=max(max_2,i-1);
}
int main()
{
scanf("%s",s);
for(int i=0;i<=strlen(s)-1;i++)
num10[i+1]=s[strlen(s)-1-i]-'0';
int now=1,maxnow=strlen(s);
for(;maxnow;)
{
if(num10[1]%2==0)
num2[now++]=0;
else num2[now++]=1;
int next=0;
int k=1;
for(int i=maxnow;i>0;i--)
{
if(num10[i]==1&&i==maxnow&&k)
{
k=0;
next=10;
maxnow--;
continue;
}
num10[i]+=next;
next=num10[i]%2*10;
num10[i]/=2;

}
}
now-=2;
for(;now>0&&!num2[now];now--);
for(int i=now;i>0;i--)
num2[i+1]=num2[i];
num2[1]=1;
now++;
num_2[1]=1;
for(int i=1;i<=now;i++)
{
if(num2[i]==1)
aplus();
multiply();
}
for(int i=maxans;i>0;i--)
printf("%d",ans[i]);
}

又一个81行……

第n个数：n=2^m-x;

则结果就是：2*x+1;

找与n最接近的2的整数次幂数，再两个数相减，外加一些7788的计算，就AC乐！

Orz zxhzxhzxhzxhzxhzxhzxhzxh神牛。。

把读入的数转换为二进制，再把首位的1移到末尾

我解释一下：

就是先找 2^i>n 然后找出上个（x=2^(i-1)）

答案是2（n-x）+1；

把n转化为二进制，去掉最高位就相当于-x；把1移到末尾就是*2+1.

.....

70行。。。。。

10遍。AC。

先找 2^i>n 然后找出上个（x=2^(i-1)）

减了(j=n-x) write（2*j+1）

112行。。一次AC秒杀

废话不是一般的多。。

稍微处理下，应该可以百行甚至90行以内。

先把读入的数转换为二进制，再把那个二进制数首位的1移到末尾，再转换回十进制输出。

第一次写这种高精。。

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

这题似乎在某年的问题求解考过

关于2^r+k的

注意二进制长度超过了255,如果用string的话会WA。

也是81行。。

细心才能AC啊