I just do maxsimum 30 iteration on my super all doing bruteforce and this give me right ans and i got ac phi(n) is not equal to number of coprime less than n, IT IS THE NUMBER OF COPRIMES LESS THAN OR EQUAL TO N. the formula of phi(n) work for all except a special number. Is it true that k=f(n), where f(n) is Euler function? Edited by author 13.02.2009 22:03 Yes =) 2 ADMINS: don't delete this hint. Really, it's easy to think it out - harder is to write If anyone got stuck with this. here is the well-known formula for computing phi function: phi(n) = product of [ p^{a - 1} * (p - 1) ], where factorized n = product [ p^a ]. The problem has a pretty fast brute force solution. Once you find a number K such that (K + 1) is prime and K divides phi(n) try to construct n with this prime (multiply by (K + 1) once and continue while phi(n) / (K + 1)^b is a multiple of (K + 1)). 144 ->185 29756 ->29929 800000000 ->1001578525 41088 ->51365 123456 ->123457 1369 ->0 369 ->0 1024 ->1285 58 ->59 21414 ->0 2000000000 ->2500015625 961 ->0 1870 ->1871 23432 ->35151 P.S. use long long (else WA7) If K=8, i.e 1,2,3,4,5,6,7,8 students. Now, each student has to sit for at least 1 lab of each professor. For N=11, Students 1 will sit in all labs, hence qualified for exam. Students 2 will sit in labs: 2,4,6,8,10,12,14,16,18,20,22. hence qualified for exam. (At least 1 lab of all Prof covered) Students 3 will sit in labs: 3,6,9,12,15,18,21,24,27,30,33 labs. hence qualified for exam. (At least 1 lab of all Prof covered) . . . Similarly Student 8 will sit in 8,16,.....,88 labs, hence qualified for exam. (At least 1 lab of all Prof covered) Please help, where I'm wrong. Just got it. N=11 will violate "exactly K students" condition. For N=11, there will be 10 students who can qualify for exams. What in 7 th test??? I've tested my inverse eiler function. It works! Try: 815799600 Output will be: 815860603 Edited by author 17.02.2016 18:48 How to pass this test? I got WA for several times. I had WA @ #85 for many times, too. Try this testcase: k = 144 The correct answer is n = 185, rather than n = 169. The same factor, 13, could NOT be used twice in different layers of search. Good luck. if k = 144 my program gives n = 185, but I got WA 85, Why ? if k = 144 my program gives n = 185, but I got WA 85, Why ? On test k=1764 my prog returns incorrect answer, but I have AC on this problem. Please, add this test. Edited by author 14.02.2009 19:58 if n=15 => k=11 and for k=8 right answer is 0! I use system("pause") to see the result. I see my program pass with a lot of numbers. But i got WA for test #5 ! any ideas ? I'm the only author submit this problem :"> Edited by author 10.01.2009 14:53 Edited by author 10.01.2009 14:53 Check more attentively your cases if output is 0. Perhaps you didn't consider some simple cases. Edited by author 10.01.2009 16:53 Edited by author 10.01.2009 16:53 |
|