| Submit | All submissions | Best solutions | Back to list |
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
| 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 |
hide comments
|
|||||
|
2021-08-31 22:07:07 David
As noted in other comments, Java I/O is slow. No existing Java solutions. Java will need more time. |
|||||
|
2015-01-27 19:51:11 Sayak Haldar
precomputation+binary search got ac with c++ Last edit: 2015-01-28 20:03:54 |
|||||
|
2014-03-09 11:38:06 Deepanker Aggarwal
Please increase time limit for JAVA |
|||||
|
2012-10-06 18:03:38 (Tjandra Satria Gunawan)(曾毅昆)
Finally AC, really hard problem :-) |
|||||
|
2012-06-25 12:18:16 Pankaj Jindal
I am getting WA, can anyone paste some large test cases or if there is any corner case.. Thanks!!! Edit: Finally AC'ed Last edit: 2012-09-27 20:15:21 |
|||||
|
2011-09-02 02:01:46 Vinay Saini
My c++ solution gives TLE while applying same concept, with haskell solution i got AC !! |
|||||
|
2011-07-04 17:43:46 Michael T
Maybe haskell's gmp saves here. It definitely does. :) Last edit: 2011-07-12 11:21:33 |
|||||
|
2011-07-04 15:46:05 hendrik
numerix: I use standard functions: ByteString.readInteger to convert and print for output. Nothing home made. Last edit: 2011-07-04 15:46:51 |
|||||
|
2011-07-04 11:48:53 numerix
hendrik: But only with efficient I/O handling, I guess. |
|||||
|
2011-07-03 22:14:03 hendrik
mukesh: never say never. For this one HASK can make it. |
|||||
RSS