首页 > 代码库 > tyvj 1934 高精度

tyvj 1934 高精度

「Poetize3」Heaven Cow与God Bull
From wwwwodddd
 
 
背景 Background
__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...
 
 
描述 Description
给定一个整数n,求一个整数m,满足m<=n,并且m/phi(m)的值最大。
注:phi(m)代表m的欧拉函数,即不大于m且与m互质的数的个数。
 
 
输入格式 InputFormat
第一行是一个整数T,表示该测试点有T组数据。
接下来T行,每行一个整数n,意义如上所述。
 
 
输出格式 OutputFormat
输出一共T行,每行一个整数m。
若对于某个n,有不止一个满足条件的m,则输出最小的m。
 
 
样例输入 SampleInput [复制数据]
 
 
样例输出 SampleOutput [复制数据]
 
 
数据范围和注释 Hint
对于10%的数据, n<=1000
对于30%的数据, n<=10^10
对于60%的数据, n<=10^2000
对于100%的数据,T<=100,n<=10^25000。
 
 
 
本题只是用来存一个高精类模板。
另外复习一下,phi(x)=x × (1-1/p1)×(1-1/p2) × ... × (1-1/pn)
本题是求 maximize {1/ [(1-1/p1)×(1-1/p2) × ... × (1-1/pn)] }
即 minimize{   (1-1/p1)×(1-1/p2) × ... × (1-1/pn)  }
然后就是水题了。
只是编的时候TLE了很久,原因是素数表开小了。
#include<iostream>#include<cstdio>#include<algorithm>#include<cstring>#include<string>#include<fstream>using namespace std;#define MAXL 10000#define VAL1 10000#define MAXN 20100class number//四位{        public:                number()                {                        clear();                }                bool is_odd()                {                        return numb[0]%2==1;                }                bool is_even()                {                        return numb[0]%2==0;                }                void lsh_bin()                {                        int i;                        for (i=topn;i>0;i--)                        {                                if (numb[i]%2==1)                                {                                        numb[i-1]+=VAL1;                                }                                numb[i]/=2;                        }                        numb[0]/=2;                        while (topn&&!numb[topn])topn--;                }                bool equal_to(int x)                {                        if (topn==0)                        {                                return x==numb[0];                        }                        if (topn==1)                        {                                return x==numb[0]+numb[1]*VAL1;                        }                        return false;                }                int size()                {                        return topn;                }                int length()                {                        int x=numb[topn];                        int ret=0;                        while (x)                        {                                ret++;                                x/=10;                        }                        int y=0;                        x=VAL1;                        while (x)                        {                                y++;                                x/=10;                        }                        y--;                        ret+=topn*y;                        return ret;                }                void operator =(int x)//{{{                {                        int now=0;                        clear();                        numb[now]=x;                        while (numb[now]>=VAL1)                        {                                numb[now+1]+=numb[now]/VAL1;                                numb[now]%=VAL1;                                now++;                                if (now>topn)topn=now;                        }                }//}}}                void operator =(number num)                {                        topn=num.topn;                        memcpy((this->numb),num.numb,sizeof(num.numb[0])*(topn+1));                }                void operator +=(number &num)//{{{                {                        int i;                        topn=max(topn,num.topn);                        for (i=0;i<=topn;i++)                        {                                numb[i]+=num.numb[i];;                                if (numb[i]>=VAL1)                                {                                        numb[i+1]+=numb[i]/VAL1;                                        numb[i]%=VAL1;                                }                        }                        while (numb[topn+1])                        {                                topn++;                                numb[topn+1]+=numb[topn]/VAL1;                                numb[topn]%=VAL1;                        }                }//}}}                void operator +=(int x)//{{{                {                        int now=0;                        if (topn==-1)topn=0;                        numb[now]+=x;                        while (numb[now]>=VAL1)                        {                                numb[now+1]+=numb[now]/VAL1;                                numb[now]%=VAL1;                                now++;                                if (now>topn)topn=now;                        }                }//}}}                void operator *=(int x)//{{{                {                        int i;                        for (i=0;i<=topn;i++)                        {                                numb[i]*=x;                        }                        for (i=0;i<=topn;i++)                        {                                if (numb[i]>=VAL1)                                {                                        numb[i+1]+=numb[i]/VAL1;                                        numb[i]%=VAL1;                                }                        }                        while (numb[topn+1])                        {                                topn++;                                numb[topn+1]+=numb[topn]/VAL1;                                numb[topn]%=VAL1;                        }                }//}}}                void operator -=(number &num)//{{{                {                        if (*this<num)throw "Error!\n->void operator -=(number &num)\n";                        int i;                        for (i=0;i<=topn;i++)                        {                                numb[i]-=num.numb[i];                        }                        for (i=0;i<=topn;i++)                        {                                while (numb[i]<0)                                {                                        numb[i]+=VAL1;                                        numb[i+1]--;                                }                        }                        while (topn&&!numb[topn])topn--;                }//}}}                void operator --(int)//{{{                {                        if (topn==0&&numb[0]==0)throw "Error!\n->void operator --(int)\n";                        int now=0;                        numb[now]--;                        while (numb[now]<0)                        {                                numb[now+1]--;                                numb[now]+=VAL1;                        }                        while (topn&&!numb[topn])topn--;                }//}}}        private:                int numb[MAXL];                int topn;                void clear()                {                        topn=0;                        memset(numb,0,sizeof(numb));                }                friend bool operator <(number num1,number num2);                friend bool operator <=(number num1,number num2);                friend bool operator ==(number num1,number num2);                friend ostream& operator <<(ostream &out,number &num);                friend istream& operator >>(istream &in,number &num);                friend number operator *(number &num1,number &num2);                friend number operator *(number num,int x);                friend number operator +(number num1,number num2);                //a=a+b远没有a+=b快};bool operator <(number num1,number num2)//{{{{        if (num1.topn!=num2.topn)        {                return num1.topn<num2.topn;        }         int i;        for (i=num1.topn;i>=0;i--)        {                if (num1.numb[i]!=num2.numb[i])                {                        return num1.numb[i]<num2.numb[i];                }        }        return false;}//}}}bool operator <=(number num1,number num2)//{{{{        if (num1.topn!=num2.topn)        {                return num1.topn<num2.topn;        }         int i;        for (i=num1.topn;i>=0;i--)        {                if (num1.numb[i]!=num2.numb[i])                {                        return num1.numb[i]<num2.numb[i];                }        }        return true;}//}}}bool operator ==(number num1,number num2)//{{{{        if (num1.topn!=num2.topn)return false;        for (int i=0;i<=num1.topn;i++)        {                if (num1.numb[i]!=num2.numb[i])return false;        }        return true;}//}}}ostream& operator <<(ostream &out,number &num)//{{{{        int i;        out<<num.numb[num.topn];        for (i=num.topn-1;i>=0;i--)        {                //压六位时        //        if (num.numb[i]<100000)out<<"0";        //        if (num.numb[i]<10000)out<<"0";                if (num.numb[i]<1000)out<<"0";                if (num.numb[i]<100)out<<"0";                if (num.numb[i]<10)out<<"0";                out<<num.numb[i];        }        return out;}//}}}istream& operator >>(istream &in,number &num)//{{{{        string str;        in>>str;        int i;        num.clear();        for (i=(int)str.length()-1,num.topn=0;i>=0;i-=4,num.topn++)        {                if (i-3<str.length())                {                        num.numb[num.topn]=(str[i]-0)+10*(str[i-1]-0)+100*(str[i-2]-0)+1000*(str[i-3]-0);                }else                {                        if (i-2<str.length())num.numb[num.topn]+=100*(str[i-2]-0);                        if (i-1<str.length())num.numb[num.topn]+=10*(str[i-1]-0);                        if (i  <str.length())num.numb[num.topn]+=(str[i]-0);                }        }        num.topn--;        return in;}//}}}number operator *(number num,int x)//{{{{        number ret;        ret=num;        ret*=x;        return ret;}//}}}number operator +(number num1,number num2)//{{{{        number ret;        ret=num1;        ret+=num2;        return ret;}//}}}number x,y,z;bool pflag[400000];int prime[10200],topp=-1;void init(){        int i,j;        for (i=2;;i++)        {                if (!pflag[i])                {                        prime[++topp]=i;                        if (topp==7100)break;                }                for (j=0;j<=topp&&prime[j]*i<400000;j++)                {                        pflag[prime[j]*i]=1;                }        }}struct aaa{        number qq;        int id;}qur[102];bool cmp1(aaa a1,aaa a2){        return a1.qq<a2.qq;}bool cmp2(aaa a1,aaa a2){        return a1.id<a2.id;}bool sved[102];int main(){        //freopen("input.txt","r",stdin);        //freopen("output.txt","w",stdout);        int n,i;        init();        cin>>n;        for (i=0;i<n;i++)        {                cin>>qur[i].qq;                qur[i].id=i;        }        z=1;    /*    for (i=0;i<6500;i++)z*=prime[i];        cout<<z.length()<<endl;;        for (i=0;i<500000;i++)        {                y=z;        }    */        sort(qur,&qur[n],cmp1);        y=1;        int now=0;        for(i=0;;i++)        {                z=y*prime[i];                while (qur[now].qq<z)                {                        qur[now].qq=y;                        now++;                        if (now==n)break;                }                if (now==n)break;                y=z;        }        sort(qur,&qur[n],cmp2);        for (i=0;i<n;i++)        {                cout<<qur[i].qq<<endl;        }}