NDIVPHI2 - N DIV PHI_N (Hard)
Given an integer N <= 1025000 find the smallest m <= N such that m/phi(m) is maximum. Where phi is Euler's totient function.
Input
The first line in the input gives the number of test cases T (T <= 200), and then T lines follow each containing an integer N.
Output
Output the smallest required value of m.
Example
Input:
1
10
Output:
6
hide comments
|
David:
2021-08-31 22:07:07
As noted in other comments, Java I/O is slow. No existing Java solutions. Java will need more time. |
|
Sayak Haldar:
2015-01-27 19:51:11
precomputation+binary search got ac with c++ Last edit: 2015-01-28 20:03:54 |
|
Deepanker Aggarwal:
2014-03-09 11:38:06
Please increase time limit for JAVA |
|
(Tjandra Satria Gunawan)(曾毅昆):
2012-10-06 18:03:38
Finally AC, really hard problem :-) |
|
Pankaj Jindal:
2012-06-25 12:18:16
I am getting WA, can anyone paste some large test cases or if there is any corner case..
|
|
Vinay Saini:
2011-09-02 02:01:46
My c++ solution gives TLE while applying same concept, with haskell solution i got AC !! |
|
Michael T:
2011-07-04 17:43:46
Maybe haskell's gmp saves here.
|
|
hendrik:
2011-07-04 15:46:05
numerix: I use standard functions: ByteString.readInteger to convert and print for output. Nothing home made. Last edit: 2011-07-04 15:46:51 |
|
numerix:
2011-07-04 11:48:53
hendrik: But only with efficient I/O handling, I guess. |
|
|
hendrik:
2011-07-03 22:14:03
mukesh: never say never. For this one HASK can make it. |
| Added by: | SALVO |
| Date: | 2010-04-23 |
| Time limit: | 1s |
| Source limit: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | ADA95 ASM32 ASM64 BASH BF C CSHARP C++ 4.3.2 CPP CPP14 C99 CLPS LISP sbcl LISP clisp D ERL FORTRAN HASK ICON ICK JAVA JS-RHINO LUA NEM NICE OCAML PAS-GPC PAS-FPC PERL PHP PIKE PRLG-swi PYTHON RUBY SCALA SCM guile SCM qobi ST TCL TEXT WHITESPACE |
| Resource: | Frank Rafael Arteaga |
RSS