Find the maximum
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65768/65768 K (Java/Others)
Total Submission(s): 1459 Accepted Submission(s): 632
Problem Description
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.
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.
Input
There are T test cases (1<=T<=50000). For each test case, standard input contains a line with 2 ≤ n ≤ 10^100.
Output
For each test case there should be single line of output answering the question posed above.
Sample Input
2 10 100
Sample Output
6 30HintIf the maximum is achieved more than once, we might pick the smallest such n.
题目大意:找出不超过n的n/phi(n)的最大值。首先要知道phi(n))表示不超过n且与n互质的正整数的个数。
解题思路:phi(x)=x(1-1/p1)(1-1/p2)(1-1/p3)(1-1/p4)…..(1-1/pn)
p1到pn是x的素因子,n/phi(n)则表示1/(1-1/p1)(1-1/p2)(1-1/p3)(1-1/p4)…..(1-1/pn),则希望素因子最多的时候分母最小,分值最大。详解见代码。
p1到pn是x的素因子,n/phi(n)则表示1/(1-1/p1)(1-1/p2)(1-1/p3)(1-1/p4)…..(1-1/pn),则希望素因子最多的时候分母最小,分值最大。详解见代码。
题目地址:Find the maximum
AC代码:
import java.util.*; import java.io.*; import java.math.*; public class Main //qixifestival { public static void main(String args[]) { int mark[],i,j; //mark为1,则表示prim mark=new int[502]; for(i=0;i<=500;i++) mark[i]=1; mark[0]=0;mark[1]=0; for(i=2;i<=25;i++) //筛选素数 { if(mark[i]==1) { for(j=i*i;j<500;j+=i) mark[j]=0; } } BigInteger prim[]; //保存素数 int t=0; prim=new BigInteger[102]; for(i=2;i<=500;i++) if(mark[i]==1) prim[++t]=BigInteger.valueOf(i); //System.out.println(t); BigInteger res[]; //保存素数积,即结果 res=new BigInteger[80]; res[1]=BigInteger.valueOf(2); for(i=2;i<56;i++) res[i]=res[i-1].multiply(prim[i]); /*String s=res[55].toString(); int len=s.length(); System.out.println(len);*/ //输出104说明55可以装下100位 Scanner cin= new Scanner(System.in); int n; n=cin.nextInt(); while(n!=0) { n--; BigInteger cur; cur=cin.nextBigInteger(); for(i=55;i>=1;i--) { if(res[i].compareTo(cur)<=0) { System.out.println(res[i]); break; } } } } } //1406MS 4144K