2015
04-14

# Find the maximum

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.

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

2
10
100

6
30

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

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

public class Main {
static final int MAX = 1000;
static BigInteger[] Ans = new BigInteger[MAX];
public static void getAns()
{
boolean[] flag = new boolean[MAX];
for(int i = 0; i < MAX; ++i)
flag[i] = true;
Ans[0] = BigInteger.ONE;
for(int i = 2; i < MAX; ++i)
{
if(flag[i])
{
for(int j = i + i; j < MAX; j += i)
{
flag[j] = false;
}
}
}
}

public static BigInteger findAns(BigInteger n)
{
int left = 1, right = 100, mid;
while(left + 1 < right)
{
mid = (left + right) >> 1;
if(Ans[mid].compareTo(n) > 0)
right = mid - 1;
else
left = mid;
}
return Ans[right].compareTo(n) <= 0 ? Ans[right] : Ans[left];
}
public static void main(String[] args) throws IOException {
//FileInputStream ios = new FileInputStream("in.txt");
//System.setIn(ios);
Scanner cin = new Scanner(System.in);
getAns();
int t = cin.nextInt();
while(t-- > 0)
{
String n = new String();
n = cin.next();
BigInteger bn = new BigInteger(n);
System.out.println(findAns(bn).toString());
}
}
}


1. 第23行：
hash = -1是否应该改成hash[s ] = -1

因为是要把从字符串s的start位到当前位在hash中重置

修改提交后能accept，但是不修改居然也能accept