Euler's Totient function, φ (n) [sometimes called the phi function], is used to determine the number of numbers less than n which are relatively prime to n . For example, as 1, 2, 4, 5, 7, and 8, are all less than nine and relatively
prime to nine, φ(9)=6.
HG is the master of X Y. One day HG wants to teachers XY something about Euler's Totient function by a mathematic game. That is HG gives a positive integer N and XY tells his master the value of 2<=n<=N for which φ(n) is a maximum. Soon HG finds that this seems
a little easy for XY who is a primer of Lupus, because XY gives the right answer very fast by a small program. So HG makes some changes. For this time XY will tells him the value of 2<=n<=N for which n/φ(n) is a maximum. This time XY meets some difficult because
he has no enough knowledge to solve this problem. Now he needs your help.

There are T test cases (1<=T<=50000). For each test case, standard input contains a line with 2 ≤ n ≤ 10^100.

For each test case there should be single line of output answering the question posed above.

2
10
100

6
30

Hint
If the maximum is achieved more than once, we might pick the smallest such n.  
 

 

这个题目其实是个水题的。

但是之前他们出题的把样例搞错了。于是一直WA。。

 

我说说我的做法吧。

这个题的目的是找n/phi(n)的最大值

 

这里可以对这个式子变下形

n/phi(n)=[p1^a1*p2^a2*...pn^an]/[phi(p1^a1)*phi(p2^a2)*...*phi(pn^an)]

由于phi(p^k)，当p为质数的时候=p^k-p^(k-1)

式子进一步化简变为：

(p1/(p1-1))*(p2/(p2-1))*...*(pn/(pn-1))

 

那么从这个式子就可以看出来，n/phi(n)的大小只与n的质因子有关

 

其实这里就得到了一个结论，要让这个式子最大，那么n就必然是一些质数的积

 

即是说：n=2*3*5*7*11*。。。。

直到最大的那个不能超过输入数据N的那儿

 

我的代码：

import java.util.*;
import java.io.*;
import java.math.*;

public class Main {
    public static void main(String args[])
    {
        Scanner cin=new Scanner(System.in);
        int i,j,num=0,t;
        BigInteger ans = null;
        long[] prime=new long[30000];
        boolean[] flag=new boolean[200000];
        BigInteger n,temp;
        for(i=0;i<200000;i++)
            flag[i]=false;
        for(i=2;i<200000;i++)
        {
            if(!flag[i])
            {
                prime[num]=i;
                num++;
                for(j=i+i;j<200000;j=j+i)
                    flag[j]=true;
            }
        }
        t=cin.nextInt();
        for(j=1;j<=t;j++)
        {
            temp=BigInteger.ONE;
            n=cin.nextBigInteger();
            for(i=0;i<num;i++)
            {
                temp=temp.multiply(BigInteger.valueOf(prime[i]));
                if(temp.compareTo(n)<=0)
                    ans=temp;
                else
                    break;
            }
            System.out.println(ans);
        }
    }
}