hdu4002 Find the maximum 歐拉函數
//求小於N且n/phi(x)最大的n如果有多個,輸出最小的
//phi(x) = x*(1-1/p1)*(1-1/p2)*(1-1/p3)....
//要使得x/phi(x) 最大，即使得(1-1/p1)*(1-1/p2)*(1-1/p3)....最小
//又p1, p2 , p3 , ....
//全為素數因子，所以可以對枚舉所有素數因子乘積，
//打表後找小於等於n的數
#include
#include
#include
using namespace std ;
const int maxn = 1010;
char str[maxn] ;
int num[maxn][maxn] ;
int num_1[maxn] ;
int len[maxn] ;
int isp[maxn] ;
int prime[maxn] ;
int set()
{
memset(isp , 0 ,sizeof(isp)) ;
isp[1] = 1;
for(int i = 4;i < maxn;i+=2)
isp[i] = 1;
for(int i = 3;i < maxn;i++)
{
if(isp[i])continue ;
for(int j = i*i;j < maxn;j+=i)
isp[j] = 1;
}
int j = 0 ;
for(int i = 1;i < maxn;i++)
if(!isp[i])prime[++j] = i ;
return j ;
}
bool cmp(int len_1 , int len_2 , int pos)
{
if(len_1 > len_2)return 0 ;
if(len_2 > len_1)return 1 ;
for(int i = len_1 ;i > 0;i--)
{
if(num_1[i] > num[pos][i])
return 0 ;
if(num_1[i] < num[pos][i])
return 1 ;
}
return 0 ;
}
void init()
{
int sum = set() ;
num[0][1] = 1;
len[0] = 1;
for(int i = 1;;i++)
{
int c = 0 ;
len[i] = len[i-1] ;
for(int j = 1;j <= len[i];j++)
{
num[i][j] = prime[i]*num[i-1][j] ;
num[i][j] += c ;
c = num[i][j]/10 ;
num[i][j] %= 10 ;
}
while(c)
{
num[i][++len[i]] = c%10 ;
c/=10 ;
}
if(len[i] > 100)break;
}
}
int main()
{
init() ;
int T ;
scanf("%d" , &T) ;
while(T--)
{
scanf("%s" , str) ;
int len_1 = strlen(str) ;
for(int i = len_1 - 1;i >= 0 ;i--)
num_1[len_1 - i] = str[i] - '0' ;
int pos = 1;
while(!cmp(len_1 , len[pos] , pos))pos++ ;
for(int i = len[pos-1];i >= 1;i--)
printf("%d" , num[pos-1][i]) ;
puts("") ;
}
}
