bzoj3034: Heaven Cow与God Bull

Description

__int64 ago,there's a heaven cow called sjy...
A god bull named wzc fell in love with her...
As an OI & MOer,wzc gave sjy a quesiton...

给定一个整数n，求一个整数m，满足m<=n，并且m/phi(m)的值最大。
注：phi(m)代表m的欧拉函数，即不大于m且与m互质的数的个数。

Input

第一行是一个整数T，表示该测试点有T组数据。
接下来T行，每行一个整数n，意义如上所述。

Output

输出一共T行，每行一个整数m。
若对于某个n，有不止一个满足条件的m，则输出最小的m。

贪心考虑，答案为质数的前缀积，筛出60000以内的质数，离线处理询问

高精度需要压位优化

#include<cstdio>

#include<cstring>

int ps[],pp=;

bool isnp[];

int T;

char str[];

int p10[]={,,,};

struct integer{

    int x[],id,ed;

    void read(){

        scanf("%s",str);

        int l=strlen(str)-;

        for(int i=;i<=l;i++){

            x[i>>]+=p10[i&]*(str[l-i]-'');

        }

    }

    void print(){

        int p=;

        while(p&&!x[p])--p;

        printf("%d",x[p]);

        for(int i=p-;~i;--i)printf("%04d",x[i]);

        putchar();

    }

    void operator*=(int a){

        for(int i=;i<;i++)x[i]*=a;

        for(int i=;i<;i++)x[i+]+=x[i]/,x[i]%=;

    }

}q[],v,v1;

bool operator>(integer&a,integer&b){

    for(int i=;~i;--i){

        if(a.x[i]!=b.x[i])return a.x[i]>b.x[i];

    }

    return ;

}

int main(){

    for(int i=;i<=;i++){

        if(!isnp[i])ps[pp++]=i;

        for(int j=;j<pp&&i*ps[j]<=;j++){

            isnp[i*ps[j]]=;

            if(i%ps[j]==)break;

        }

    }

    scanf("%d",&T);

    for(int i=;i<T;i++){

        q[i].id=i;

        q[i].read();

    }

    v.x[]=v1.x[]=;

    for(int i=;i<pp;i++){

        v*=ps[i];

        for(int j=;j<T;j++)if(!q[j].ed&&v>q[j]){

            q[j]=v1;

            q[j].ed=;

        }

        v1=v;

    }

    for(int i=;i<T;i++){

        for(int j=;j<T;j++)if(q[j].id==i){

            q[j].print();

        }

    }

    return ;

}