首页 > 代码库 > lightoj 1097

lightoj 1097

2024-09-16 12:34:13   217人阅读

1097 - Lucky Number

 
 

Lucky numbers are defined by a variation of the well-known sieve of Eratosthenes. Beginning with the natural numbers strike out all even ones, leaving the odd numbers 1, 3, 5, 7, 9, 11, 13, ... The second number is 3, next strike out every third number, leaving 1, 3, 7, 9, 13, ... The third number is 7, next strike out every seventh number and continue this process infinite number of times. The numbers surviving are called lucky numbers. The first few lucky numbers are:

1, 3, 7, 9, 13, 15, 21, 25, 31, 33, ...

In this problem your task is to find the nth lucky number where n is given in input.

Input

Input starts with an integer T (≤ 10000), denoting the number of test cases.

Each case contains an integer n (1 ≤ n ≤ 105).

Output

For each case, print the case number and the nth lucky number.

Sample Input

Output for Sample Input

2

2

100000

Case 1: 3

Case 2: 1429431

 

 

#include<iostream>
#include<cstdio>
using namespace std;
const int MAXN=1500000;
struct node
{
    int l,r,sum;
}tree[MAXN*3];
void pushup(int o)
{
    tree[o].sum=tree[o<<1].sum+tree[o<<1|1].sum;
}
void build(int l,int r,int o)
{
    tree[o].l=l,tree[o].r=r;
    if(l==r)
    {
        tree[o].sum=l&1;
        return;
    }
    int mid=(l+r)>>1;
    build(l,mid,o<<1);
    build(mid+1,r,o<<1|1);
    pushup(o);
}
int query(int pos,int o)
{
    if(tree[o].l==tree[o].r)return tree[o].l;
    if(pos<=tree[o<<1].sum)return query(pos,o<<1);
    else return query(pos-tree[o<<1].sum,o<<1|1);
}
void update(int pos,int o)
{
    if(tree[o].l==tree[o].r){tree[o].sum=0;return;}
    if(pos<=tree[o<<1].sum)update(pos,o<<1);
    else update(pos-tree[o<<1].sum,o<<1|1);
    pushup(o);
}
void table()
{
    int cnt=0;
    build(1,1429431,1);
    for(int i=2;i<=100000;i++)
    {
        int v=query(i,1);
        for(int j=v;v+j<=1429431;j+=v-1)
            update(j,1);
    }
}
int main()
{
    table();
    int T;
    scanf("%d",&T);
    for(int kase=1;kase<=T;kase++)
    {
        int n;
        scanf("%d",&n);
        printf("Case %d: %d\n",kase,query(n,1));
    }
    return 0;
}

 

lightoj 1097


联系
我们