Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65768/65768 K (Java/Others)
Total Submission(s): 1731 Accepted Submission(s): 742
容易看出如果一个数x含有越多质因子的话 ， phi(x) 就约小 ， 那么 x / phi(x) 便更大 。
原题的解就变成了求 2 ~ n 之内尽量大的前面的质数的乘积。
不知道为什么写暴力会RE 。 打表就AC了。。应该写得丑了 。
暴力打表的程序 ：
#include <iostream> #include <algorithm> #include <cstdio> #include <cmath> #include <cstring> #include <vector> #include <map> #include <vector> #include <queue> using namespace std ; typedef long long LL ; typedef pair<int,int> pii; #define X first #define Y second const int N = 50100 ; struct node { string s ; int id ; } e[N]; int prime[1000010] ,tot ; bool check[1000010]; string Mul( string s , int a ) { int c = 0 ; for( int i = 0 ; i < s.length() ; ++i ) { c = ( s[i] - ‘0‘ ) * a + c ; s[i] = (char)( c % 10 ) + ‘0‘ ; c /= 10 ; } while( c > 0 ) { s += (char)( c % 10 + ‘0‘ ) ; c /= 10 ; } return s; } void Output( string s ) { for( int j = s.length() - 1 ; j >=0 ; --j ) cout << s[j] ; } inline bool Compare( const string a , const string b ) { if( a.length() < b.length() ) return true ; else if( a.length() > b.length() ) return false ; else { for( int i = a.length() - 1 ; i >= 0 ; --i ){ if( a[i] > b[i] ) return false ; else if( b[i] > a[i] )return true ; } return true ; } } int main () { #ifdef LOCAL // freopen("in.txt","r",stdin); freopen("out.txt","w",stdout); #endif // LOCAL tot = 0 ; for( int i = 2 ; i < 1000000 ; ++i ) if( !check[i] ){ prime[tot++] = i ; for( int j = i + i ; j < 1000000 ; j += i ) check[j] = true ; } string s = "1" , str = "" , ans = "1" ; int cnt = 0 ; for( int i = 1 ; i < 100 ; ++i ) str += "0" ; str += "1"; while( Compare( s , str ) ) { s = Mul( s , prime[cnt++] ); cout <<‘"‘; Output(s); cout <<"\"\,"<<endl; } }
表 (AC程序)：
#include <iostream> #include <algorithm> #include <cstdio> #include <cmath> #include <cstring> #include <vector> #include <map> #include <vector> #include <queue> using namespace std ; char s[][550] = { "2", "6", "30", "210", "2310", "30030", "510510", "9699690", "223092870", "6469693230", "200560490130", "7420738134810", "304250263527210", "13082761331670030", "614889782588491410", "32589158477190044730", "1922760350154212639070", "117288381359406970983270", "7858321551080267055879090", "557940830126698960967415390", "40729680599249024150621323470", "3217644767340672907899084554130", "267064515689275851355624017992790", "23768741896345550770650537601358310", "2305567963945518424753102147331756070", "232862364358497360900063316880507363070", "23984823528925228172706521638692258396210", "2566376117594999414479597815340071648394470", "279734996817854936178276161872067809674997230", "31610054640417607788145206291543662493274686990", "4014476939333036189094441199026045136645885247730", "525896479052627740771371797072411912900610967452630", "72047817630210000485677936198920432067383702541010310", "10014646650599190067509233131649940057366334653200433090", "1492182350939279320058875736615841068547583863326864530410", "225319534991831177328890236228992001350685163362356544091910", "35375166993717494840635767087951744212057570647889977422429870", "5766152219975951659023630035336134306565384015606066319856068810", "962947420735983927056946215901134429196419130606213075415963491270", "166589903787325219380851695350896256250980509594874862046961683989710", "29819592777931214269172453467810429868925511217482600306406141434158090", "5397346292805549782720214077673687806275517530364350655459511599582614290", "1030893141925860008499560888835674370998623848299590975192766715520279329390", "198962376391690981640415251545285153602734402721821058212203976095413910572270", "39195588149163123383161804554421175259738677336198748467804183290796540382737190", "7799922041683461553249199106329813876687996789903550945093032474868511536164700810", "1645783550795210387735581011435590727981167322669649249414629852197255934130751870910", "367009731827331916465034565550136732339800312955331782619462457039988073311157667212930", "83311209124804345037562846379881038241134671040860314654617977748077292641632790457335110", "19078266889580195013601891820992757757219839668357012055907516904309700014933909014729740190", "4445236185272185438169240794291312557432222642727183809026451438704160103479600800432029464270", "1062411448280052319722448549835623701226301211611796930357321893850294264731624591303255041960530", "256041159035492609053110100510385311995538591998443060216114576417920917800321526504084465112487730", "64266330917908644872330635228106713310880186591609208114244758680898150367880703152525200743234420230" }; int main () { int _ ; scanf("%d",&_) ; char s1[550]; int len[54] ; for( int i = 0 ; i < 54 ; ++i ) len[i] = strlen(s[i]); while( _-- ) { scanf("%s",s1); int id = 0 ; int slen = strlen(s1); for( int i = 0 ; i < 54 ; ++i ) { if( len[i] < slen ) id = i ; else if( len[i] > slen ) break ; else { if( strcmp( s1 , s[i]) >= 0 ) id = i ; else break ; } } printf("%s\n",s[id]); } }
原文：http://www.cnblogs.com/hlmark/p/4296752.html
