首页 > ACM题库 > HDU-杭电 > HDU 4002-Find the maximum-高精度-[解题报告]HOJ
2015
04-14

HDU 4002-Find the maximum-高精度-[解题报告]HOJ

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

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

题目:Find the maximum

题意:

如题。

解题思路:

打表后不难找出一条规律:要找的那个数总是2*3*5*7*…这样的值,用递推方法求出所有范围内的这些素数积,从中用二分找出符合的数就行了。比赛的时候,小杰用其独藏的C++高精度模版写了个,TLE,然后cxyue用java过掉了。当时我说用二分查找优化下啊,cxyue说才100个数,二分没多大用,后来那天晚上,小杰跟我说他100多ms过掉了,用了二分。不懂java,下面是鄙人对着类库敲出来的AC代码。顺便一说,为什么类成员变量要定义为static呢,因为只有static数据成员才能被static成员函数调用,main函数是static的。

 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];
         int primeNumber = 0;
         for(int i = 0; i < MAX; ++i)
             flag[i] = true;
         Ans[0] = BigInteger.ONE;
         for(int i = 2; i < MAX; ++i)
         {
             if(flag[i])
             {
                 ++primeNumber;
                 Ans[primeNumber] = Ans[primeNumber - 1].multiply(BigInteger.valueOf(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());
         }
     }
 }

参考:http://www.cnblogs.com/Kenfly/archive/2011/09/09/2172422.html


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

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

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