「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...
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互质的数的个数。
注：phi(m)代表m的欧拉函数，即不大于m且与m互质的数的个数。
输入格式 InputFormat
第一行是一个整数T，表示该测试点有T组数据。
接下来T行，每行一个整数n，意义如上所述。
接下来T行，每行一个整数n，意义如上所述。
输出格式 OutputFormat
输出一共T行，每行一个整数m。
若对于某个n，有不止一个满足条件的m，则输出最小的m。
若对于某个n，有不止一个满足条件的m，则输出最小的m。
数据范围和注释 Hint
对于10%的数据, n<=1000
对于30%的数据, n<=10^10
对于60%的数据, n<=10^2000
对于100%的数据，T<=100，n<=10^25000。
对于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 20100 class 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! ->void operator -=(number &num) "; 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! ->void operator --(int) "; 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; } }