HOJ 1016 Joseph's problem I 树状数组求第K大

HOJ 1016 Joseph's problem I

My Tags	(Edit)

	Source : Unknown
	Time limit : 10 sec		Memory limit : 32 M

Submitted : 1484, Accepted : 439

The Joseph's problem is notoriously known. For those who are not familiar with the problem, among n people numbered 1,2...n, standing in circle every m_th is going to be executed and only the life of the last remaining person will be saved. Joseph was smart enough to choose the position of the last remaining person, thus saving his life to give the message about the incident.

Although many good programmers have been saved since Joseph spread out this information, Joseph's cousin introduced a new variant of the malignant game. This insane character is known for its barbarian ideas and wishes to clean up the world from silly programmers. We had to infiltrate some the agents of the ACM in order to know the process in this new mortal game.

In order to save yourself from this evil practice, you must develop a tool capable of predicting which person will be saved.

The Destructive Process

The persons are eliminated in a very peculiar order; m is a dynamical variable, which each time takes a different value corresponding to the prime numbers' succession (2,3,5,7...). So in order to kill the ith person, Joseph's cousin counts up to the i_th prime.

Input

It consists of separate lines containing n [1..3501], and finishes with a 0.

Output

The output will consist in separate lines containing the position of the person which life will be saved.

Sample Input

Sample Output

题目：
约瑟夫环问题，不过第k次的间隔为第k个素数

分析：
先用筛法筛选出所有的素数，然后再用树状数组求第K大。不过数据量比较大，所
以对于每个输入数据都求一遍的话，会TLE。。。所以我们可以先把3501个都存在
一个数组中，每次询问的时候直接以O(1)的时间输出

#include <vector>
#include <cstdio>
#include <cstring>
#include <iostream>

using namespace std;

typedef long long ll;

#define debug puts("here");

const int X = 3605;
const int MAXM = 36005;

vector<int> prime;
bool use[MAXM];
int c[X];

void init(){
    memset(use,false,sizeof(use));
    prime.push_back(2);
    for(int i=3;i<MAXM;i+=2)
        if(!use[i]){
            prime.push_back(i);
            for(int j=i+i;j<MAXM;j+=i)
                use[j] = true;
        }
}

int lowbit(int x){
    return x & -x;
}

void modify(int x,int num){
    while(x<X){
        c[x] += num;
        x += lowbit(x);
    }
}

int query(int x){
    int ret = 0;
    while(x>0){
        ret += c[x];
        x -= lowbit(x);
    }
    return ret;
}

void binary(int n,int k){
    int l = 1,r = n;
    while(l<=r){
        int mid = (l+r)>>1;
        int temp = query(mid);
        if(temp>=k)
            r = mid-1;
        else
            l = mid+1;
    }
    modify(l,-1);
}

int ans[X];

int main(){

#ifndef ONLINE_JUDGE
    freopen("sum.in","r",stdin);
    //freopen("sum.out","w",stdout);
#endif

    int op = 3600; // 控制
    init();
    int n;
    for(n=1;n<op;n++){
        memset(c,0,sizeof(c));
        for(int i=1;i<=n;i++)
            modify(i,1);
        int pre = 1;
        int res = n;
        for(int i=0;i<n-1;i++){
            pre = (prime[i]+pre-2)%res+1;
            binary(n,pre);
            res --;
        }
        for(int i=1;i<=n;i++)
            if(c[i]){
                ans[n] = i;
                break;
            }
    }
    while(scanf("%d",&n),n)
        printf("%d\n",ans[n]);
    return 0;
}