Find the maximum
Time Limit: 2000/1000 MS (Java/Others)Memory Limit: 65768/65768 K (Java/Others)
Total Submission(s): 132Accepted Submission(s): 63
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.
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
Sample Output
6
30
Hint
If the maximum is achieved more than once, we might pick the smallest such n.
Source
这个题目其实是个水题的。
但是之前他们出题的把样例搞错了。于是一直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的那儿
我的代码:
分享到:
相关推荐
收集的部分HDOJ杭电ACM题的代码 大牛勿下 全是基础供初级acmer使用
自己积累的部分杭电oj的(hdu)解题代码。。大家有空来看看。 基本上是自己写的哈。有错误之处请指教、
HDOJ,2011阿里巴巴程序设计公开赛的标程 题目位置:http://acm.hdu.edu.cn/vip/2011alibaba/index.php
杭电oj4405,一道简单的概率dp题目
杭电acm解题报告 详细解析2000-2099 适合acm初学者
ACM ICPC HDOJ1000
思路:这个题和HDU - 5703类似,其实就是拆数问题,一个数的拆法其实就是2^(N-1),具体证明过程可以直接搜刚才杭电那道题的题解,所以这道题其实就是让你算2^(N-1),但是题目给的N特别大, 可以达到10^100000,我们...
杭州电子科技大学hdoj1002,大整数相加问题
hdu 期末考试复习资料 计算机网络 编译原理 计算机图形学 编译原理 信息安全与技术 数据库应用系统开发
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
压缩包包含十份报告,已经通过验收,实验内容:交换机、生成树、静态路由、NAT等完全根据教材实验要求
hdoj的一些题目分类,由hdu大牛搜集,希望对做ac的同志们有帮助
杭电ACMhdu1163
HDU1059的代码
ACM ICPC HDOJ 1005
hdu1001解题报告
hdu 1574 passed sorce
HDU ACM 2005第几天 C++ http://acm.hdu.edu.cn/listproblem.php?vol=11 2005题 第几天?
HDU的一题........HDU DP动态规